题解 [牛客练习赛61D] 最短路变短了

• 最短路变短了

题目描述

给定一个有向带权图，每次询问将一条边反向会不会使 的最短路变短。

正解

先以 1 号点为源点在正图跑最短路，第 个点的距离记为 。

再以 号点为源点在反图跑最短路，第 个点的距离记为 。

设 号边为有序三元组 。（题目给定的）

修改 号边，最短路变短当且仅当 。

为啥呢？

如果不走 号边，那么最短路显然不会变短。

如果走 号边，那么最短路一定是 。

#include <bits/stdc++.h>
#define N 200005

using namespace std;

int n, m, q;
int u[N], v[N], w[N];
int head[N], nex[N], to[N], eVal[N], ecnt;
long long dist[2][N];

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}
inline void addE(int u, int v, int w) {
    to[++ecnt] = v, eVal[ecnt] = w;
    nex[ecnt] = head[u], head[u] = ecnt;
}

struct node {
    int id;
    long long dist;
    bool operator > (const node &t) const {
        return dist > t.dist;
    }
};
void spfa(int str, long long *dist) {
    priority_queue<node, vector<node>, greater<node> > que;
    memset(dist, 32, (n + 1) * 8);
    dist[str] = 0;
    que.push((node){str, 0});
    while(!que.empty()) {
        node cur = que.top(); que.pop();
        if(cur.dist != dist[cur.id]) continue;
        int u = cur.id;
        for(int i = head[u], v; i; i = nex[i]) {
            v = to[i];
            if(dist[v] > dist[u] + eVal[i]) {
                dist[v] = dist[u] + eVal[i];
                que.push((node){v, dist[v]});
            }
        }
    }
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) {
        u[i] = read(), v[i] = read(), w[i] = read();
        addE(u[i], v[i], w[i]);
    }

    spfa(1, dist[0]);

    ecnt = 0;
    memset(head, 0, sizeof head);
    for(int i = 1; i <= m; ++i)
        addE(v[i], u[i], w[i]);
    spfa(n, dist[1]);

    q = read();
    while(q--) {
        int i = read();
        puts(dist[0][n] > dist[0][v[i]] + w[i] + dist[1][u[i]] ? "YES" : "NO");
    }
    return 0;
}

小彩蛋 : 有发现我的 SPFA 跑的其实是 Dijkstra 吗？