题目描述
一张图，有由T个节点，R条双向边和P条单向边组成，每条边有边权且可能存在负权，求能否从S到达每个节点并且输出最小花费。
思路
首先第一想法，把这张图建出来，在跑一遍spfa即可，然而它显然被卡了，不过似乎可以用双端队列优化水过去。
接下就是正解。我们考虑对于所有的道路，都是正权，我们可以用Dijkstra做，而对于航线，不存在环。因此，如果我们将道路相连的连通图缩点之后，得到必定是DAG，而DAG显然可以用拓扑排序更新最短路。
所以我们只需要先把双向边的图建出来，跑一遍tarjan缩点，再进行toposort，每次更新时把连通块中所有节点都加入Dijkstra的优先队列中，对于每个点进行更新dis数组。在进行Dijkstra时把单向边也更新一遍即可。
代码
#include<bits/stdc++.h> using namespace std; const int N=250020,M=1e5+10; const int INF=0x3f3f3f3f; int head[N],tot,to[M],nxt[M],w[M]; void add_edge(int x,int y,int z) //双向边建图 { nxt[++tot]=head[x]; head[x]=tot; to[tot]=y; w[tot]=z; } int dfn[N],top,idx,st[N],low[N]; int co[N],col; vector<int>g[N]; bool vis[N]; void tarjan(int u) //tarjan缩点 { dfn[u]=low[u]=++idx; st[++top]=u; for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { co[u]=++col; g[col].push_back(u); //记录每个连通块的节点 while(st[top]!=u) { co[st[top]]=col; g[col].push_back(st[top]); top--; } top--; } } int dis[N]; priority_queue<pair<int,int> >q; queue<int> que; int fir[N],cnt,nex[M],ed[M],c[M],in[N]; void add(int x,int y,int z) //单向边建图 { nex[++cnt]=fir[x]; fir[x]=cnt; ed[cnt]=y; c[cnt]=z; } void Dijkstra() { while(!q.empty()) { int u=q.top().second;q.pop(); if(vis[u])continue ; vis[u]=1; for(int i=head[u];i;i=nxt[i]) { int v=to[i]; if(dis[u]<INF&&dis[v]>dis[u]+w[i]) { dis[v]=dis[u]+w[i]; q.push(make_pair(-dis[v],v)); } } for(int i=fir[u];i;i=nex[i]) //更新单向边 { int v=ed[i]; if(dis[u]<INF&&dis[v]>dis[u]+c[i]) dis[v]=dis[u]+c[i]; //不加入优先队列 in[co[v]]--; if(!in[co[v]])que.push(co[v]); } } } void toposort(int s) { memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=col;i++) if(!in[i])que.push(i); dis[s]=0; while(!que.empty()) { int u=que.front();que.pop(); for(int i=0;i<g[u].size();i++) //更新连通块 { int v=g[u][i]; q.push(make_pair(-dis[v],v)); } Dijkstra(); } } int read() { int res=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();} return res*w; } void write(int x) { if(x<0){putchar('-');x=-x;} if(x>9)write(x/10); putchar(x%10^48); } void writeln(int x) { write(x); putchar(' '); } int main() { // freopen("a.txt","r",stdin); // freopen("aa.txt","w",stdout); int t=read(); int r=read(),p=read(),s=read(); for(int i=1;i<=r;i++) { int u=read(),v=read(),w=read(); add_edge(u,v,w);add_edge(v,u,w); } for(int i=1;i<=t;i++) if(!dfn[i])tarjan(i); for(int i=1;i<=p;i++) { int u=read(),v=read(),w=read(); add(u,v,w); if(co[u]!=co[v])in[co[v]]++; } toposort(s); for(int i=1;i<=t;i++) if(dis[i]==INF)puts("NO PATH"); else writeln(dis[i]); }