【题解】道路与航线

快三个月没更了。。。(没有理由,就是懒

道路与航线

这道题目是一道神题,一个小错误能查半天,但是如果做出来,代码能力应该可以有显著提升。

总共调了我一个星期,里面有很多个坑点。(我最后做出来是随便改了一下,然后就出人意料地过了)

题意概述

现在有给你一幅图,有R条无向边,P条有向边。其中 $R<5e5$ , $P<5e5$

解题思路

$5e5+1e6$ 就是 $1.5*10^6$ 条边,用SPFA直接跑跑不过(除了SPFA的玄学优化据说可以过)。但是dij是可以过的,所以我们考虑将这个图转成一个正权图。

这里我们先只读入无向边,并将所有用无向边连在一起的放到一个连通块中,用有向边连接连通块。然后对这些连通块拓扑排序,在这里拓扑排序是用来判断哪个连通块最先跑。

dij的时间复杂度是 $O((E+V)log(E+V))$,SPFA最坏情况是O(VE)。而这道题目就正好卡了SPFA。

我们会发现,在每一个连通块中,都是正权了,除了和其他连通块相连的点。但是这个没有关系,因为它出现下图的情况不会出现错误。
博客配图.png

代码&各种错误

#include<bits/stdc++.h>
using namespace std;
int T,R,P,S;
int head[25005];
vector<int> G[25005];
struct e{
    int nxt,to,sum;
}edge[150005];
int tot;
void add_edge(int u,int v,int w){
    tot++;
    edge[tot].nxt=head[u];
    edge[tot].to=v;
    edge[tot].sum=w;
    head[u]=tot;
    return ;
}
int vis[25005];
int cnt=0;
int c[25005];
void DFS(int now){
    vis[now]=1;
    c[now]=cnt;
    G[cnt].push_back(now);
    for(int i=head[now];i;i=edge[i].nxt){
        if(!vis[edge[i].to])DFS(edge[i].to);
    }
}
int ru[25005];
int dis[25005],viss[25005];
struct node{
    int v,w;
};
struct cmp{
    bool operator () (node aa,node bb){
        return aa.w>bb.w;
    }
};
queue<int> q;
void dij(int start){
    priority_queue<node,vector<node>,cmp> qq;
    node now,nxt;
    for(vector<int>::iterator it=G[start].begin();it<G[start].end();it++){
        now.v=*it,now.w=dis[*it];
        qq.push(now);
    }
    while(!qq.empty()){
        now=qq.top();
        qq.pop();
        if(viss[now.v])continue;
        viss[now.v]=1;
        for(int i=head[now.v];i;i=edge[i].nxt){
            nxt.v=edge[i].to;
            if(c[nxt.v]!=start){//这个地方不能写道dis[nxt.v]>dis[now.v]+edge[i].sum判断里面,因为无论有没有松弛,都要将边断开。
                ru[c[nxt.v]]--;
                if(!ru[c[nxt.v]])q.push(c[nxt.v]);
            }
            if(dis[nxt.v]>dis[now.v]+edge[i].sum){
                dis[nxt.v]=dis[now.v]+edge[i].sum;
                nxt.w=dis[nxt.v];
                if(c[nxt.v]==start)qq.push(nxt);
            }
        }
    }
}
void topu(){
    q.push(c[S]);
    ru[c[S]]=-1;//这个地方一定要设成-1,否则会自己加自己
    for(int i=1;i<=cnt;i++){
        if(ru[i]==0&&i!=c[S]){
            q.push(i);
        }
    }
    int now,nxt;
    while(!q.empty()){
        now=q.front();
        q.pop();
        dij(now);
        ru[now]=-1;
    }
}
int main(){
    for(int i=0;i<25005;i++)dis[i]=2000000007;//有的时候999999999会太小了不够用,所以干脆开到2e9
    scanf("%d%d%d%d",&T,&R,&P,&S);
    int u,v,w;
    for(int i=1;i<=R;i++){
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    for(int i=1;i<=T;i++){
        if(!vis[i]){
            ++cnt;
            DFS(i);
        }
    }
    for(int i=1;i<=P;i++){
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);
        ru[c[v]]++;
    }
    dis[S]=0;
    topu();
    for(int i=1;i<=T;i++){
        if(dis[i]>1000000007)printf("NO PATH\n");
        else printf("%d\n",dis[i]);
    }
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/656/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者