Find Dining (USACO Gold 2018 December)

题意是图上一些节点有价值（美味度） $y_i$ ，问从每个点 $j$ 出发，是否存在有一个价值 $>0$ 的点 $i$ ，使得 $j$ 走到 $i$ 再走到 $N$ 的最短距离，不大于直接从 $j$ 到 $N$ 的最短距离加上 $y_i$ 。

最直观的做法就是把所有两两点的最短路都算出来，但这个肯定会超时，因为是 $\mathcal{O}(N^3)$ 。

这时候我们需要思考，图上的思维题，标准方法不管用的时候，常用的路数就是修改原图（比如Favorite Colors），这里也是一样。正解是用两个Dijkstra，后一个在修改的图上运行:

先在原图跑Dijkstra，得到从 $N$ 到所有点的最短距离。
然后在修改图上Dijkstra: 增加一个节点 $N+1$ ，把有干草的点到 $N+1$ 之间加边，边长是 $\text{shortest\_distance}[i]-y[i]$ 。Dijkstra的起点是 $N+1$ 。这个的意思是，这次要求一定要经过有干草的节点，从“新的 $N$ ”（就是 $N+1$ ）出发，先加上到干草节点的距离，再减掉美味值，就可以计算出强制走过干草节点的“等价距离”。
比较新的dist[i]，如果和第一个Dijkstra相比距离相等或减少，就输出1，否则输出0。
新增的边可能是负的，但因为所有负环都包含 $N+1$ ，所以不影响结果。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
 
int n, m, K;
vector<pii> adj[50005];     // target, time (<=1e4)
int dist1[50005], dist2[50005];
int id[50005];
int y[50005];               // <= 1e9
 
void dijkstra(int s, int *dist) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({0,s});
    fill(dist, dist+n+1, 1e9);
    dist[s] = 0;
    vector<bool> vis(n+1, false);
    while (!q.empty()) {
        int u = q.top().second, du = q.top().first;
        q.pop();
        if (du != dist[u]) continue;
        if (vis[u]) continue;
        vis[u] = true;          // visit each node at most once
        for (auto p: adj[u]) {
            int v = p.first, dv = p.second;
            if (dist[u] + dv < dist[v]) {
                dist[v] = dist[u] + dv;
                q.push({dist[v], v});
            }
        }
    }
}
 
int main() {
    scanf("%d %d %d", &n, &m, &K);
    for (int i = 0; i < m; i++) {
        int u,v,d;
        scanf("%d %d %d", &u, &v, &d);
        u--; v--;
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    for (int i = 0; i < K; i++) {
        scanf("%d %d", &id[i], &y[i]);
        id[i]--;
    }
    dijkstra(n-1, dist1);
    for (int i = 0; i < K; i++) {   // add edges from haybales to n
        int u = id[i];
        int d = dist1[u] - y[i];
        adj[u].push_back({n,d});
        adj[n].push_back({u,d});
    }
    dijkstra(n, dist2);             // 2nd dijkstra
    for (int i = 0; i < n-1; i++)
        if (dist2[i] <= dist1[i])
            printf("1\n");
        else
            printf("0\n");
    return 0;
}