AcWing 道路与航线

时隔1年，看到我当年写的题解，还是打算来改改。然后我也回复了评论里同学的问题（抱歉太久没上AcWing了）

大致的思路，我下面的题解和lyd老师的书上都写的很清楚了。我就来讲讲几个很多人踩到的坑（以前也讲过，这次举个例子大家就一目了然了）

坑1：为什么一开始要加入入度为0的点？

• 因为要保证拓扑序列的进行。假设s所在块编号为a，a连向块c，块b连向块c，且块a块b不相连。此时，如果你不加入入度为0的点，那么b块就不会访问到，c的入度也就不会减到0，也就不会访问到。

坑2：判断无解为什么不写出==inf？

• 因为有坑1的存在。还是上面那个例子，再加2个条件：
  1. 块d->块b，块a与块d不相连。
  2. d到b的路为负边权
  • 此时显然应该块b、d里所有的点都是NOPATH，而且dis都为inf。但其实在用块d内的点更新块b时，会松弛成功，因为存在负边权。所以无解时不一定dis就为inf

评论1：

• 额。我1年前定义queue、stack、vector都是在子函数里定义都没问题。
• 但是我可以确定的是，多了的话是会爆空间的。（有一次手残在dfs里定义vector
  所以我优化了代码，见下文。因为dij的结束条件是队列为空，所以结束时队列其实就是清空了的。所以定义在外边就行。

评论2：

• 是的，dij的确是每做一次就确定一个点的最短路。换句话说，就是你说的：“每一个点只能拓展一次”。但是可以注意到，一开始我将块内点加入的时候并没有给他们打上vis标记。因此如果他们再次松弛的话还是可以被加入队列。
• 总结一下：
  • 当一个点一开始被加入队列时，是因为不确定连通块内的哪个点可以作为起点
  • 当一开始加入的点再次被加入队列时，是为了进行后续的松弛操作

评论3：

• 评论3里犀首大大说得很好了，跟我想的一样。也就是2L同学的问题。

评论4：

• 不可以直接从s开始拓扑。我知道你想的是如果一个点没访问到就NOPATH。但是这样做会导致拓扑无法完成。理由同坑点1。

代码逻辑整体优化了许多，见下。还有，一年前的在这写的题解我就不在AcWing放出来了。这样篇幅太长看着不舒服。我就丢个链接吧传送门

说点题外话，今天偶然上了AcWing。突然发现一年了我还是辣么菜，从提高二等混到省选rank9（还是没进队就是了QwQ，关键是，我在GX（留下了蒻省的泪水）

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int N=25005;
const int M=50005;

struct E {int nex,to,dis;} e[M*3];
int n,m1,m2,s,num,tot;
int h[N],bel[N],in[N],dis[N];
bool vis[N];
vector<int> p[N];
queue<int> q;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > que;

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*10+c-'0'; c=getchar();}
    return x*f;
}

void add(int u,int v,int w) {e[++num]={h[u],v,w},h[u]=num;}

void dfs(int x) {
    bel[x]=tot,p[tot].push_back(x);
    for(int i=h[x];i;i=e[i].nex)
        if(!bel[e[i].to]) dfs(e[i].to);
}

void dijkstra(int block) {
    for(int size=p[block].size(),i=0;i<size;i++) {
        int x=p[block][i];
        que.push(make_pair(dis[x],x));
    }
    while(que.size()) {
        int x=que.top().second; que.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=h[x];i;i=e[i].nex) {
            int y=e[i].to;
            if(dis[x]+e[i].dis<dis[y]) {
                dis[y]=dis[x]+e[i].dis;
                if(!vis[y] && bel[x]==bel[y]) que.push(make_pair(dis[y],y));
            }
            if(bel[x]!=bel[y]) {
                in[bel[y]]--;
                if(!in[bel[y]]) q.push(bel[y]);
            }
        }
    }
}

int main()
{
    cin>>n>>m1>>m2>>s;
    for(int i=1;i<=m1;i++) {
        int u=read(),v=read(),w=read();
        add(u,v,w),add(v,u,w);
    }
    for(int i=1;i<=n;i++)
        if(!bel[i]) tot++,dfs(i);
    for(int i=1;i<=m2;i++) {
        int u=read(),v=read(),w=read();
        add(u,v,w),in[bel[v]]++;
    }
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,q.push(bel[s]);
    for(int i=1;i<=tot;i++)
        if(!in[i]) q.push(i);
    while(q.size()) {
        int block=q.front(); q.pop();
        dijkstra(block);
    }
    for(int i=1;i<=n;i++) {
        if(dis[i]>=1e9) printf("NO PATH\n");
        else printf("%d\n",dis[i]);
    }
    return 0;
}