这篇文章上次修改于 464 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
本文共 2268 个字，阅读时长 ≈ 6 分钟

P3008 [USACO11JAN] Roads and Planes G

题目链接

题意

一个 N 个点的图，有 R 条道路和 P 条航线。道路是无向边，边权保证为正数；航线是有向边，边权有可能有负数，且保证如果存在从 u 到 v 的航线，从 v 无法到达 u。求 s 到 n 个点的单源最短路，如果无法到达输出 NO PATH

思路

这道题里我们需要关注两个重要的性质，第一个是无向边的边权保证为正数，第二个是如果存在从 u 到 v 的航线，从 v 无法到达 u。既然题目分了无向和有向边，无向边边权又保证为正数，我们可以把无向边组成的连通块缩成一个点然后在这个连通块内用 dij 跑最短路，这就利用了第一个性质。第二个性质我们可以把它转化为拓扑来理解，既然我们已经缩完点，再加上第二个性质，新图就是一个有向无环图，我们可以利用拓扑排序跑最短路即可。

为什么缩点可行呢，因为有向边保证了不能回来，我们可以考虑把所有有向边删掉，这样就会形成一个个连通块，我们将连通块缩点并每个连通块跑最短路，最后加上有向边拓扑排序跑最短路即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue> 
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=25003,M=150005,inf=1<<29;
int n,m1,m2,s,h,t;
typedef pair<int,int> pii;
vector<pii> p[N],r[N];
vector<int> cnt[N];
int bl[N],q[N],dis[N],rd[N];
bool vis[N];
void bfs(int x,int col){
    h=t=0;
    q[++t]=x;
    bl[x]=col;
    cnt[col].push_back(x);
    int u;
    while(h<t){
        u=q[++h];
        for(pii v:r[u])
            //在入队时直接设置belong，为了去重
            if(!bl[v.first]) q[++t]=v.first,bl[v.first]=col,cnt[col].push_back(v.first);
    }
}
priority_queue<pii,vector<pii>,greater<pii> > pq;
void dij(int x){
    while(!pq.empty()) pq.pop();
    pii now;
    int u,v;
    //dij这里要把这个块内所有更新过dis的都入队
    for(int i:cnt[x])
        if(dis[i]<inf) pq.emplace((pii){dis[i],i});
    while(!pq.empty()){
        now=pq.top();
        pq.pop();
        u=now.second;
        if(vis[u]) continue;
        vis[u]=1;
        for(pii e:r[u]){
            v=e.first;
            if(dis[v]>dis[u]+e.second){
                dis[v]=dis[u]+e.second;
                if(!vis[v]) pq.emplace((pii){dis[v],v});
            }
        }
        //顺便把这个点延伸出来的有向边的终点的dis更新一下
        //这里因为只用min更新所以跟dij没关系，因为之后不管这个点了才放这的
        for(pii e:p[u]){
            dis[e.first]=min(dis[e.first],dis[u]+e.second);
        }
    }
}
int main()
{
    n=read();
    m1=read();
    m2=read();
    s=read();
    //加一个无向边一个有向边
    for(int i=1;i<=m1;++i){
        int u=read(),v=read(),w=read();
        r[u].emplace_back((pii){v,w});
        r[v].emplace_back((pii){u,w});
    }
    for(int i=1;i<=m2;++i){
        int u=read(),v=read(),w=read();
        p[u].emplace_back((pii){v,w});
    }
    //bfs染色缩点
    int col=0;
    for(int i=1;i<=n;++i)
        if(!bl[i]) bfs(i,++col);
    //统计入度，准备拓扑
    for(int i=1;i<=n;++i)
        for(pii v:p[i]) ++rd[bl[v.first]];
    for(int i=0;i<=n;++i) dis[i]=inf;
    h=t=0;
    dis[s]=0;
    //拓扑排序，找入度为0的块
    for(int i=1;i<=col;++i)
        if(!rd[i]) q[++t]=i;
    int tmp;
    while(h<t){
        tmp=q[++h];
        dij(tmp);
        //更新入度
        for(int i:cnt[tmp]){
            for(pii v:p[i])
                if(--rd[bl[v.first]]==0) q[++t]=bl[v.first];
        }
    }
    //输出
    for(int i=1;i<=n;++i){
        if(dis[i]==inf) printf("NO PATH\n");
        else printf("%d\n",dis[i]);
    }
    return 0;
}