题目

image-20210318200457249

题意

给定t个点,r条道路,p条航线,和一个起点,道路可互相到达,航线只能单向到达,且航线的权值可能为负数,问从起点到各个点的最小距离是多少?若不可到达输出“NO PATH”

思路

把所有道路相连的点组成联通块,给他们编上号,从起点所在的联通块往后跑一个拓扑排序,连通块内跑dijstla,松弛时发现松驰的点和当前点不在一个连通块内,则把更新的点所在的联通块入度-1,大致思路是这样,但是还是有许多细节问题

  1. 为什么一开始要加入入度为0的点?
    • 因为要保证拓扑序列的进行。假设s所在块编号为a,a连向块c,块b连向块c,且块a块b不相连。此时,如果你不加入入度为0的点,那么b块就不会访问到,c的入度也就不会减到0,也就不会访问到。
  2. 判断无解为什么不写出==inf?
    • 因为有坑1的存在。还是上面那个例子,再加2个条件:
      1. 块d->块b,块a与块d不相连。
      2. d到b的路为负边权
        • 此时显然应该块b、d里所有的点都是NOPATH,而且dis都为inf。但其实在用块d内的点更新块b时,会松弛成功,因为存在负边权。所以无解时不一定dis就为inf
  3. 对每一个连通块跑最短路时,不知道那个点作为起点,理论上是最小的那个点,但是考虑到可能从一个联通块到当前联通块距离比较小,但是从起点所在的联通块到当前联通块距离较大,但是两条路不相交,即不可互相到达,这样会导致起点到这个联通块的路径反而消失了,所以把所有点放到优先队列里才是合适的做法

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int MAXN=500000;
const int INF=0x3f3f3f3f;
struct node{
int to,next,w;
}e[MAXN];
struct Node{
int u,d;
bool operator<(const Node &o)const{
return d>o.d;
}
};
int head[MAXN],dis[MAXN],id[MAXN],in[MAXN];
int n,r,p,s,tot,bcnt;
bool vis[MAXN];
vector<int> ve[MAXN];
queue<int> q;
priority_queue<Node> pq;
void add(int u,int v,int w){
e[tot]={v,head[u],w};
head[u]=tot++;
}
void dfs(int x){
ve[bcnt].push_back(x);
id[x]=bcnt;
for(int i=head[x];~i;i=e[i].next){
if(!id[e[i].to]) dfs(e[i].to);
}
}
void dij(int s){
for(auto i:ve[s]) pq.push({i,dis[i]});
while(!pq.empty()){
Node now=pq.top();
pq.pop();
if(vis[now.u]) continue;
vis[now.u]=1;
for(int i=head[now.u];~i;i=e[i].next){
int v=e[i].to,w=e[i].w;
if(dis[v]>dis[now.u]+w){
dis[v]=dis[now.u]+w;
if(id[v]==id[now.u]) pq.push({v,dis[v]});
}
if(id[v]!=id[now.u]){
in[id[v]]--;
if(in[id[v]]==0) q.push(id[v]);
}
}
}
}
void tupo(){
memset(dis,0x3f,sizeof dis);
dis[s]=0;
q.push(id[s]);
for(int i=1;i<=bcnt;i++){
if(!in[i]) q.push(i);
}
while(!q.empty()){
int fr=q.front();
q.pop();
dij(fr);
}
}
int main()
{
ios;
memset(head,-1,sizeof head);
cin>>n>>r>>p>>s;
while(r--){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
for(int i=1;i<=n;i++){
if(!id[i]){
bcnt++;
dfs(i);
}
}
while(p--){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
in[id[v]]++;
}
tupo();
for(int i=1;i<=n;i++){
if(dis[i]>INF/2) cout<<"NO PATH"<<'\n'; //可能存在到不了的点却被负权边更新了
else cout<<dis[i]<<'\n';
}
return 0;
}