题目描述
这是个链接
思路分析
- 题意很明确，求带负边的最短路。
诶，别上去就跑 spfa 啊，这可是 USACO。
- 众所周知，USACO 喜欢卡 (spfa)，可是有负边有不能用 (Dijkstra) ，这怎么搞？
- 还是先说一下 (Dijkstra) 为什么不能跑负边吧。(Dijkstra) 的核心是由贪心得来的，即长边是有最短的边松弛的，而在有负边的图中，因为负边不论多长都会使长边更短，所以贪心不成立
- 但是这道题的负边很特殊，是单向的，如果先不考虑负边的呢？那么这时候整个图的联通性是无法保证的，会形成许多个由无向边形成的联通块。
- 在联通块内没有负边，所以是可以跑 (Dijkstra) 的，其实这时加上负边，对不同的联通块跑 (Dijkstra) 也是不会出问题的，因为这条负边是桥，也就是不可或却、必定经过的。
- 接下来就很简单了，用拓扑排序依次更新每个联通块。哦，对了，题目给了中心城市，所以先把中心城市所在的联通块加进去
(Code)
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#define R register
#define N 200010
using namespace std;
inline int read(){
int x = 0,f = 1;
char ch = getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int n,r,p,s,cnt,head[N],dis[N],in[N],belong[N];
bool vis[N];
struct edge{
int to,next,dis;
}e[N<<2];
int len;
void addedge(int u,int v,int w){
e[++len].to = v;
e[len].dis = w;
e[len].next = head[u];
head[u] = len;
}
vector<int>sta[N];
void dfs(int u){//求出每个点所在的联通块
belong[u] = cnt;
sta[cnt].push_back(u);
for(R int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(belong[v])continue;
dfs(v);
}
}
struct node{
int dis,id;
node(){}
node(int _dis,int _id){dis = _dis,id = _id;}
inline bool operator <(const node &a)const{
return dis > a.dis;
}
};
priority_queue<node>q;
queue<int>qq;
void Dij(){
while(!q.empty()){
int u = q.top().id;q.pop();
if(vis[u])continue;
vis[u] = 1;
for(R int i = head[u];i;i = e[i].next){
int v = e[i].to;
if(dis[v]>dis[u]+e[i].dis){
dis[v] = dis[u] + e[i].dis;
if(belong[u]==belong[v])q.push(node(dis[v],v));
}
if(belong[u]!=belong[v]){
in[belong[v]]--;
if(!in[belong[v]])qq.push(belong[v]);
}
}
}
}
void Topo(){//拓扑排序以此更新每个联通块最短路
qq.push(belong[s]);
for(R int i = 1;i <= cnt;i++)if(!in[i])qq.push(i);
memset(dis,0x7f,sizeof(dis));//0x3f会wa的
dis[s] = 0;
while(!qq.empty()){
int u = qq.front();qq.pop();
for(R int i = 0;i < sta[u].size();i++)q.push(node(dis[sta[u][i]],sta[u][i]));
Dij();
}
}
int main(){
n = read(),r = read(),p = read(),s = read();
for(R int i = 1;i <= r;i++){
int a = read(),b = read(),c = read();
addedge(a,b,c);
addedge(b,a,c);
}
for(R int i = 1;i <= n;i++){
if(!belong[i]){
cnt++;
dfs(i);
}
}
for(R int i = 1;i <= p;i++){
int a = read(),b = read(),c = read();
in[belong[b]]++;//入度++
addedge(a,b,c);
}
Topo();
for(R int i = 1;i <= n;i++){
if(dis[i]>=0x3f3f3f3f)puts("NO PATH");
else printf("%d
",dis[i]);
}
return 0;
}