考察:最短路+拓扑排序
完全不会,fw本f
错误思路:
一看题,这不spfa裸题吗,结果代码上去TLE.
正确思路:
有负权边求最短路,又卡SPFA.不考虑SPFA优化的话,似乎是没有办法了.但这道题特地说明了两种边的特性,所以可以从边入手.
已知双向边无负权边,如果不考虑单向边可以考虑用dijkstra算法.又已知单向边只存在A->B的方式,一定不存在B->A的方式.当我们不考虑单向边,剩下的就是离散的连通块.我们将连通块缩点,再加入单向边.由于单向边不成环,最后一点可以形成拓扑排序.拓扑排序的最短路可以按拓扑排序的顺序求即可.
那么如何实现上述思路?因为需要考虑拓扑排序,所以按拓扑排序处理,先将入度为0的连通块纳入队列,然后更新该连通块内的最短距离.如果当前点能遍历到其他连通块的点,那么该连通块入度-1,直到入度=0,纳入拓扑队列.
注意几个坑点:
- 不能直接把起点所在连通块放入,这样存在无法更新拓扑序列的情况.
- 不能在dist[v]>dist[u]+w的if内判断入度是否为0.按照拓扑排序应该只要能遍历到入度就--.否则后面的连通块不能更新.
- 虽然拓扑排序入度可能>1.但是实际图只要有边就可以遍历到其他连通块去,其他块的距离必须被更新,所以只要能遍历到,入度就--
1 #include <iostream>
2 #include <cstring>
3 #include <queue>
4 #include <vector>
5 using namespace std;
6 const int N = 25010,M = 50010,INF = 0x3f3f3f3f;
7 typedef pair<int,int> PII;
8 int n,m,sx,s,h[N],idx,dist[N],p[N],id[N],d[N],sz;
9 bool st[N];
10 vector<int> node[N];
11 struct Road{
12 int fr,to,ne,w;
13 }road[M*3];
14 void add(int a,int b,int w)
15 {
16 road[idx].to = b,road[idx].w = w,road[idx].ne = h[a],h[a] = idx++;
17 }
18 void dfs(int u,int color)
19 {
20 id[u] = color;
21 st[u] = 1;
22 node[color].push_back(u);
23 for(int i=h[u];i!=-1;i=road[i].ne)
24 {
25 int v = road[i].to;
26 if(!st[v]) dfs(v,color);
27 }
28 }
29 void dijkstra(int idx)
30 {
31 priority_queue<PII,vector<PII>,greater<PII> > q;
32 for(int i=0;i<node[idx].size();i++) q.push({dist[node[idx][i]],node[idx][i]});
33 while(q.size())
34 {
35 PII it = q.top();
36 q.pop();
37 int u = it.second;
38 if(st[u]) continue;
39 st[u] = 1;
40 for(int i=h[u];~i;i=road[i].ne)
41 {
42 int v = road[i].to;
43 if(id[v]!=id[u])
44 if(--d[id[v]]==0) node[0].push_back(id[v]);
45 if(dist[v]>dist[u]+road[i].w)
46 {
47 dist[v] = dist[u]+road[i].w;
48 if(id[v]==id[u]) q.push({dist[v],v});
49 }
50 }
51 }
52 }
53 void solve()
54 {
55 memset(dist,0x3f,sizeof dist);
56 dist[s] = 0;
57 queue<int> q;
58 for(int i=1;i<=sz;i++)
59 if(!d[i]) q.push(i);
60 while(q.size())
61 {
62 int u = q.front();
63 q.pop();
64 dijkstra(u);
65 for(int i=0;i<node[0].size();i++) q.push(node[0][i]);
66 node[0].clear();
67 }
68 }
69 int main()
70 {
71 scanf("%d%d%d%d",&n,&m,&sx,&s);
72 memset(h,-1,sizeof h);
73 while(m--)
74 {
75 int a,b,c; scanf("%d%d%d",&a,&b,&c);
76 add(a,b,c); add(b,a,c);
77 }
78 for(int i=1;i<=n;i++)
79 if(!id[i]) dfs(i,++sz);
80 memset(st,0,sizeof st);
81 while(sx--)
82 {
83 int a,b,c; scanf("%d%d%d",&a,&b,&c);
84 add(a,b,c); d[id[b]]++;
85 }
86 solve();
87 for(int i=1;i<=n;i++)
88 if(dist[i]>=INF/2) puts("NO PATH");
89 else printf("%d\n",dist[i]);
90 return 0;
91 }