题目

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;
}