洛谷P7984 [USACO21DEC] Tickets P 题解

题意：

Bessie 正在参加远足旅行！她当前正在旅行的路线由编号为 \(1\ldots N\)（\(1\le N\le 10^5\)）的 \(N\) 个检查点组成。

有 \(K~(1\le K\le 10^5)\) 张票可供购买。第 \(i\) 张票可以在检查站 \(c_i~(1\le c_i\le N)\) 以 \(p_i~(1\le p_i\le 10^9)\) 的价格购得，并且可以用其进入所有检查站 \([a_i,b_i]\)（\(1\le a_i\le b_i\le N\)）。在进入任何检查站之前，Bessie 必须已购买一张允许其进入该检查站的票。一旦 Bessie 可以前往某一检查站，她就可以在未来的任何时候回到该检查站。

对于每一个 \(i\in [1,N]\)，如果 Bessie 最初只能进入检查点 \(i\)，输出使得可以进入检查点 \(1\) 和 \(N\) 所需的最低总价。如果无法这样做，输出 \(-1\)。

输入格式：

输入的第一行包含 \(N\) 和 \(K\)。

以下 \(K\) 行，对于每一个 \(1\le i\le K\)，第 \(i\) 行包含四个整数 \(c_i,p_i,a_i\) 和 \(b_i\)。

输出格式：

输出 \(N\) 行，每行输出一个检查点的答案。

设 \(f_i\) 为以 \(i\) 为起点的答案，那么 \[ f_i = \min\left\{f_j + w(i, j)\mid (i, j) \in E\right\} \] 初值 \(f_i = \mathrm{dis}(i,1) + \mathrm{dis}(i, n)\) 。

显然这是一个最短路更新 dp 的形式。考虑用线段树优化建图，然后跑 Dijkstra 。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef pair<ll, int> pii;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(3e6 + 15))
#define ls(at) tr[at].ls
#define rs(at) tr[at].rs
#define Fi first
#define Se second

ll d[N], a[N]; priority_queue<pii> q;
int n, m, rt, tot, o, pos = 1, head[N], vis[N]; 
struct Edge { int v, w, next; } e[N];
struct node { int l, r, ls, rs; } tr[N];
void addEdge(int u, int v, int w) { e[++pos] = {v, w, head[u]}; head[u] = pos; }
int build(int l, int r)
{
    if(l == r) return tr[l].l = l, tr[l].r = r, l;
    int at = ++tot, mid = (l + r) >> 1;
    tr[at].l = l, tr[at].r = r;
    ls(at) = build(l, mid); rs(at) = build(mid + 1, r);
    addEdge(ls(at), at, 0); addEdge(rs(at), at, 0); return at;
}
void update(int nl, int nr, int k, int at = rt)
{
    if(nl <= tr[at].l && tr[at].r <= nr) return addEdge(at, k, 0);
    int mid = (tr[at].l + tr[at].r) >> 1;
    if(nl <= mid) update(nl, nr, k, ls(at));
    if(nr > mid) update(nl, nr, k, rs(at));
}
void Dijkstra(int s, int type)
{
    q = {};
    if(type) {
        rep(i, 1, tot + o) d[i] = INF;
        d[s] = 0; q.push({0ll, s});
    }else {
        rep(i, 1, tot + o) { d[i] = a[i], q.push({-d[i], i}); }
    }
    static int tim = 0; ++tim;
    while(!q.empty())
    {
        while(!q.empty() && vis[q.top().Se] == tim) q.pop();
        if(q.empty()) break;
        int u = q.top().Se; q.pop(); vis[u] = tim;
        for(int i = head[u], v; i; i = e[i].next)
            if(d[v = e[i].v] > d[u] + e[i].w) { d[v] = d[u] + e[i].w; q.push({-d[v], v}); }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; tot = n; rt = build(1, n);
    rep(i, 1, m)
    {
        static int c, p, l, r; cin >> c >> p >> l >> r;
        ++o; update(l, r, o + tot); addEdge(o + tot, c, p);
    }
    Dijkstra(1, 1); rep(i, 1, tot + o) a[i] += d[i];
    Dijkstra(n, 1); rep(i, 1, tot + o) a[i] += d[i];
    Dijkstra(0, 0); rep(i, 1, n) { cout << (d[i] <= INF / 2 ? d[i] : -1) << '\n'; }
    return 0;
}