题解 [牛客练习赛61D] 最短路变短了
最短路变短了
https://ac.nowcoder.com/acm/contest/5026/D
题目描述
给定一个有向带权图,每次询问将一条边反向会不会使 的最短路变短。
正解
先以 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 吗?