# 题目
# 题意
给定 t 个点，r 条道路，p 条航线，和一个起点，道路可互相到达，航线只能单向到达，且航线的权值可能为负数，问从起点到各个点的最小距离是多少？若不可到达输出 “NO PATH”
# 思路
把所有道路相连的点组成联通块，给他们编上号，从起点所在的联通块往后跑一个拓扑排序，连通块内跑 dijstla，松弛时发现松驰的点和当前点不在一个连通块内，则把更新的点所在的联通块入度 - 1，大致思路是这样，但是还是有许多细节问题
- 为什么一开始要加入入度为 0 的点？
- 因为要保证拓扑序列的进行。假设 s 所在块编号为 a，a 连向块 c，块 b 连向块 c，且块 a 块 b 不相连。此时，如果你不加入入度为 0 的点，那么 b 块就不会访问到，c 的入度也就不会减到 0，也就不会访问到。
- 判断无解为什么不写出 ==inf？
- 因为有坑 1 的存在。还是上面那个例子，再加 2 个条件：
- 块 d-> 块 b，块 a 与块 d 不相连。
- d 到 b 的路为负边权
- 此时显然应该块 b、d 里所有的点都是 NOPATH，而且 dis 都为 inf。但其实在用块 d 内的点更新块 b 时，会松弛成功，因为存在负边权。所以无解时不一定 dis 就为 inf
- 因为有坑 1 的存在。还是上面那个例子，再加 2 个条件：
- 对每一个连通块跑最短路时，不知道那个点作为起点，理论上是最小的那个点，但是考虑到可能从一个联通块到当前联通块距离比较小，但是从起点所在的联通块到当前联通块距离较大，但是两条路不相交，即不可互相到达，这样会导致起点到这个联通块的路径反而消失了，所以把所有点放到优先队列里才是合适的做法
# CODE
#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; | |
} |
