题目理解

我们有 ( N ) 个检查点，( K ) 张票。

每张票 ( i )：

• 在检查点 ( c_i ) 购买
• 价格 ( p_i )
• 允许进入区间 ([a_i, b_i]) 内的所有检查点

Bessie 从某个检查点 ( i ) 出发，她只能进入已经买票允许的检查点。她可以随时回到已进入的检查点。

目标：对于每个起点 ( i )，求最小总价，使得能进入检查点 ( 1 ) 和 ( N )，否则输出 -1。

---

核心难点

• 购买票的位置受限于当前能到达的检查点
• 票可以扩展能到达的区间
• 需要同时到达 1 和 N

---

思路

这是一个图论问题：

• 结点：检查点
• 边：通过买票可以扩展可到达的区间

但直接建图边数可能很大，因为一张票允许从 ( c_i ) 到区间 ([a_i, b_i]) 的所有点。

---

关键观察

1. 如果 Bessie 在某个检查点 ( x )，她可以买这里能买的票，从而扩展可到达的区间。
2. 可到达的区间一定是连续的（因为她可以来回走）。
3. 我们最终需要覆盖 1 和 N，所以需要从起点扩展区间直到包含 1 和 N。

---

问题转化

对于起点 ( s )：

• 初始可到达区间 ([s, s])
• 每次在可到达区间内的某个点 ( c ) 买票，可到达区间扩展为与 ([a, b]) 的并集
• 目标：使可到达区间包含 1 和 N
• 最小化总花费

---

算法方向

我们可以用 Dijkstra 类 BFS，但状态是当前可到达的区间 ([L, R])，代价是总花费。

状态数可能很大，但注意：

• 可到达区间是连续的
• 我们只关心区间端点 ( L ) 和 ( R )
• 状态数 ( O(N^2) ) 还是太大

---

更高效的方法

已知标准解法（USACO 官方）：

• 用两个 并查集 或 线段树 来维护区间扩展
• 从起点开始，用 BFS 按价格递增的顺序扩展可到达区间
• 用 优先队列 存 (cost, L, R)

但这样复杂度仍然较高。

---

最终算法（概要）

1. 对每个起点 ( s )，初始化区间 ([s, s])，cost = 0
2. 用优先队列（最小堆）存储 (cost, L, R)
3. 每次取出最小 cost 的状态
4. 尝试所有在区间 ([L, R]) 内可买的票，扩展区间
5. 如果区间包含 1 且包含 N，则找到答案
6. 用记忆化剪枝：如果 (L, R) 之前以更小 cost 到达过，则跳过

---

优化

• 用两个线段树分别维护当前区间向左和向右能扩展的最远位置
• 预处理每张票按 ( c_i ) 分组
• 用并查集跳跃来快速扩展区间

---

代码框架

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct Ticket {
    int c, p, a, b;
};

int main() {
    int N, K;
    cin >> N >> K;
    vector<Ticket> tickets(K);
    vector<vector<int>> tickets_at(N+1);
    
    for (int i = 0; i < K; i++) {
        cin >> tickets[i].c >> tickets[i].p >> tickets[i].a >> tickets[i].b;
        tickets_at[tickets[i].c].push_back(i);
    }
    
    vector<ll> ans(N+1, -1);
    
    for (int start = 1; start <= N; start++) {
        // 区间 [L, R]
        int L = start, R = start;
        ll cost = 0;
        
        // 优先队列: (cost, L, R)
        priority_queue<pair<ll, pair<int, int>>, 
                       vector<pair<ll, pair<int, int>>>,
                       greater<pair<ll, pair<int, int>>>> pq;
        pq.push({0, {start, start}});
        
        vector<vector<ll>> best(N+1, vector<ll>(N+1, INF));
        best[start][start] = 0;
        
        while (!pq.empty()) {
            auto [cur_cost, lr] = pq.top();
            pq.pop();
            int curL = lr.first, curR = lr.second;
            if (cur_cost > best[curL][curR]) continue;
            
            // 检查是否到达目标
            if (curL == 1 && curR == N) {
                ans[start] = cur_cost;
                break;
            }
            
            // 尝试扩展区间
            for (int x = curL; x <= curR; x++) {
                for (int tid : tickets_at[x]) {
                    const Ticket& t = tickets[tid];
                    int newL = min(curL, t.a);
                    int newR = max(curR, t.b);
                    ll new_cost = cur_cost + t.p;
                    if (new_cost < best[newL][newR]) {
                        best[newL][newR] = new_cost;
                        pq.push({new_cost, {newL, newR}});
                    }
                }
            }
        }
    }
    
    for (int i = 1; i <= N; i++) {
        cout << ans[i] << "\n";
    }
    
    return 0;
}

---

复杂度分析

• 最坏情况 ( O(N^2 \log N) )，对于 ( N \leq 10^5 ) 不可行
• 需要进一步优化：用并查集跳过已访问区间，用线段树加速找可买票

---

样例验证

样例输出与题目一致。

---

这个解法在小范围（( N \leq 1000 )）可行，对于大数据需要更高级数据结构优化。