Moo Route II (USACO Silver 2023 February)

基本的图遍历 / 最短路问题。

令 $\text{ans}[i]$ 表示每个节点 $i$ 的最早到达时间。初始化所有 $\text{ans}[i]$ 为最大值（ $10^9 + 1$ ），并将节点 $1$ 加入队列 $q$ 。
每次从队列 $q$ 取出节点 $v$ ，检查所有从 $v$ 出发的边 $j$ 。如果该边“可用”（即 $\text{ans}[v] + w[v] \leq r_j$ ），则用 $s_j$ 更新 $\text{ans}[d_j]$ ，并将 $d_j$ 加入队列。
重复上述过程直到队列为空。
朴素实现会在第 14 个测试点后 TLE，因为某些边会被多次访问。实际上每条边只需处理一次。我们可以将每个节点 $c$ 的所有出边按 $r$ 从小到大排序，然后按 $r$ 递减顺序处理，并在处理后删除这些边。

时间复杂度 $O(N+M)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
struct E {
    int r,d,s;
};
 
int n, m;
vector<E> adj[200005];
int a[200005];
int ans[200005];
 
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int c,r,d,s;
        scanf("%d %d %d %d", &c, &r, &d, &s);
        adj[c].push_back({r,d,s});
    }
    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end(), [](const E& a, const E& b) {
            return a.r < b.r;
        });
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        ans[i] = 1e9 + 1;
    }
    ans[1] = 0;
    queue<int> q;
    q.push(0);
 
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        int w = a[v];
        if (v == 0) v = 1;          // v is 0 if we are at the start
        int i = adj[v].size() - 1;
        for (; i >= 0; i--) {
            E e = adj[v][i];
            if (ans[v] + w > e.r) break;
            if (ans[e.d] > e.s) {   // found better ans for e.d
                ans[e.d] = e.s;
                if (adj[e.d].size() > 0)
                    q.push(e.d);
            }
        }
        adj[v].resize(i+1);         // delete edges after processing
    }
 
    for (int i = 1; i <= n; i++) {
        printf("%d\n", ans[i] == 1e9 + 1 ? -1 : ans[i]);
    }
 
    return 0;
}