给定一个图 求单源最短路
这个图双向边一定是非负的 而且单向边一定不在环中
题目数据特殊构造 spfa过不了
看到图的性质 很容易想到用拓扑排序来求 但是图中只有双向边
而双向边是非负的 可以用dij来求
因此可以考虑双向边缩点之后拓扑排序
策略: 混合图缩点
在dij的时候可以顺便处理拓扑关系
//dij只能在双向边上用
//拓扑只能在单向边上用 考虑单双向连通块分开
//适用于这种有比较强性质的混合图
//在dij的时候顺便进行拓扑处理
//初始距离不是0的dij
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define pa pair<int,int>
#define mp make_pair
#define pb push_back
using namespace std;
const int N=25010;
const int M=2e5+10;
const int INF=0x3f3f3f3f;
int read()
{
int x=0,f=0,c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return f?-x:x;
}
struct Edge
{
int to,next,w;
}e[M];
int head[N],cnt;
void _add(int a,int b,int c){ e[++cnt]=(Edge){b,head[a],c}; head[a]=cnt;}
void add(int a,int b,int c){_add(a,b,c);_add(b,a,c);}
int n,m1,m2,s;
bool vis[N],used[N];
int c[N],tot,deg[N],dis[N];
vector<int> b[N];
void dfs(int x,int num)
{
c[x]=num; b[num].pb(x);
vis[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(vis[y]) continue;
dfs(y,num);
}
}
queue<int> q;
priority_queue< pa > h;
void dij(int num)
{
while(h.size()) h.pop();
for(int i=0;i<b[num].size();i++)
{
int x=b[num][i];
h.push( mp(-dis[x],x));
}
while(h.size())
{
int x=h.top().second; h.pop();
if(used[x]) continue;
used[x]=1;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if(c[x]!=c[y])
{
deg[c[y]]--; //deg[c[y]]
if(dis[x]!=INF) dis[y]=min(dis[y],dis[x]+e[i].w);
if(!deg[c[y]]) q.push(c[y]);
}
else if(dis[y]>dis[x]+e[i].w)
{
dis[y]=dis[x]+e[i].w;
h.push( mp(-dis[y],y) );
}
}
}
}
void topo()
{
memset(dis,0x3f,sizeof dis);
q.push(c[s]); dis[s]=0;
for(int i=1;i<=tot;i++)
if(!deg[i]) q.push(i);
while(q.size())
{
int x=q.front(); q.pop();
dij(x);
}
}
int main()
{
n=read(); m1=read(); m2=read(); s=read();
for(int i=1;i<=m1;i++)
{
int x=read(),y=read(),z=read();
add(x,y,z);
}
for(int i=1;i<=n;i++)
if(!vis[i]) dfs(i,++tot);
for(int i=1;i<=m2;i++)
{
int x=read(),y=read(),z=read();
_add(x,y,z);
if(c[x]!=c[y]) deg[c[y]]++;
}
topo();
for(int i=1;i<=n;i++)
dis[i]==INF?puts("NO PATH"):printf("%d\n",dis[i]);
return 0;
}
特别要注意的是:
开始要把所有入度为0的点都入队 特别的 c[s] 也要入队
否则可能有的地方就遍历不到
此外 要注意不能拿inf更新inf
所以应当特判