AcWing 道路与航线
Description
Farmer John正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到T个城镇 (1 <= T <= 25,000)，编号为1T。这些城镇之间通过R条道路 (1 <= R <= 50,000，编号为1到R) 和P条航线 (1 <= P <= 50,000，编号为1到P) 连接。每条道路i或者航线i连接城镇A_i (1 <= A_i <= T)到B_i (1 <= B_i <= T)，花费为C_i。
对于道路，0 <= C_i <= 10,000;然而航线的花费很神奇，花费C_i可能是负数(-10,000 <= C_i <= 10,000)。道路是双向的，可以从A_i到B_i，也可以从B_i到A_i，花费都是C_i。然而航线与之不同，只可以从A_i到B_i。
事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台 了一些政策保证：如果有一条航线可以从A_i到B_i，那么保证不可能通过一些道路和航线从B_i回到A_i。由于FJ的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇S(1 <= S <= T) 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。
Input
* Line 1: Four space separated integers: T, R, P, and S
* Lines 2..R+1: Three space separated integers describing a road: A_i, B_i and C_i
* Lines R+2..R+P+1: Three space separated integers describing a plane: A_i, B_i and C_i
Output
- Lines 1..T: The minimum cost to get from town S to town i, or 'NO PATH' if this is not possible
Sample Input
6 3 3 4 1 2 5 3 4 5 5 6 10 3 5 -100 4 6 -100 1 3 -10
Sample Output
NO PATH NO PATH 5 0 -95 -100
题解：
- 最短路。
- 有负边权，spfa呗。但是最坏会被卡成O(nm)，对于这题明显不行。所以思考用别的方法。
- 这题很特别，给了很多限定条件：
- “然而航线的花费很神奇，花费C_i可能是负数” -> 有负边权
- “如果有一条航线可以从A_i到B_i，那么保证不可能通过一些道路和航线从B_i回到A_i” -> 不存在负环，有可能有正环
- 再想想每个最短路算法的特点。spfa可以有负边权，不能有环。dijkstra不能有负边权。
- 那么这题我们可以只把双向边添加进来，这样就会形成若干个连通的块，块内用dijkstra跑最短路。再将单向边添加进来，就变成了一个DAG，块与块衔接部分用拓扑序跑最短路。
- 还有几个要注意的地方：
- 拓扑排序是保证可以按顺序更新，不产生紊乱。并不是用拓扑像以往的题跑dp去算。
- 因为块内算dij时，可能会更新到块外的点，这个时候就已经在算块与块间的最短路了。
- 入度为0的块要一起加进来，不能只加s所在块，因为要保证拓扑排序的进行。
- 由于第2点的存在，可能存在某个点被s不能走到的点更新。因此最后判断无解的时候不能写成==inf
- 具体算法流程参照lyd老师的讲解。
#include#include #include #include #include #define N 25005#define M 200005using namespace std;struct Node{ int val, pos; friend bool operator < (Node x, Node y) { return x.val > y.val; }};struct E {int next, to, dis;} e[M];int n, m1, m2, s, num, dfn;int h[N], bel[N], deg[N], dis[N];bool vis[N];vector c[N];queue que;int read(){ int x = 0, f = 1; char c = getchar(); while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x *= f;}void add(int u, int v, int w){ e[++num].next = h[u]; e[num].to = v; e[num].dis = w; h[u] = num;}void dfs(int x){ bel[x] = dfn, vis[x] = 1, c[dfn].push_back(x); for(int i = h[x]; i != 0; i = e[i].next) if(!vis[e[i].to]) dfs(e[i].to);}void dijkstra(int id){ priority_queue pue; for(int i = 0; i < c[id].size(); i++) pue.push((Node){dis[c[id][i]], c[id][i]}); while(pue.size()) { int now = pue.top().pos; pue.pop(); if(vis[now]) continue; vis[now] = 1; for(int i = h[now]; i != 0; i = e[i].next) { if(dis[now] + e[i].dis < dis[e[i].to]) { dis[e[i].to] = dis[now] + e[i].dis; if(bel[now] == bel[e[i].to]) pue.push((Node){dis[e[i].to], e[i].to}); } deg[bel[e[i].to]]--; if(!deg[bel[e[i].to]] && bel[now] != bel[e[i].to]) que.push(bel[e[i].to]); } }}int main(){ cin >> n >> m1 >> m2 >> s; for(int i = 1; i <= m1; i++) { int u = read(), v = read(), w = read(); add(u, v, w), add(v, u, w); } for(int i = 1; i <= n; i++) if(!vis[i]) ++dfn, dfs(i); for(int i = 1; i <= m2; i++) { int u = read(), v = read(), w = read(); add(u, v, w); deg[bel[v]]++; } memset(vis, 0, sizeof(vis)); memset(dis, 0x3f, sizeof(dis)); dis[s] = 0, que.push(bel[s]); for(int i = 1; i <= dfn; i++) if(!deg[i]) que.push(i); while(que.size()) { int now = que.front(); que.pop(); dijkstra(now); } for(int i = 1; i <= n; i++) if(dis[i] >= 1e9) printf("NO PATH\n"); else printf("%d\n", dis[i]);}