题解：P14618 [2019 KAIST RUN Fall] Lexicographically Minimum Walk

· · 题解

请注意，此题为有向图。

做题思路

因为此题是有向图，所以用并查集会 WA。

我们考虑搜索两遍。

第一遍从节点 t 开始搜索反向图，看看哪些节点可以达到 t 节点。

如果 s 节点到达不了 t 节点，输出 IMPOSSIBLE。

然后搜索第二遍，从 s 结点开始搜索。

如果有环，直接输出 TOO LONG。

搜到 t 节点时，输出路径。

因为节点数量远远小于 10^6，因此不用考虑路径太长的问题。

记得排序。

代码

:::success[这里]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define paii pair<int,int>
#define pb push_back
#define mp make_pair
#define bg begin
#define ed end
#define LEN 1000010
#define N 100010
#define M 300010
int n,m,s,t;
vector<paii> edge[N];
vector<int> not_edge[N];// 反向建图
bool is_exper[N];
void can(int u){// 判断节点 t 可以从哪些点达到
    is_exper[u]=1;
    for(auto v:not_edge[u])
        if(!is_exper[v])
            can(v);
}
int way[LEN];// 路径
bool cnt[N];// 是否经过
void dfs(int u,int deep){// 搜索
    if(cnt[u]){// 有环
        cout<<"TOO LONG\n";
        exit(0);
    }
    if(u==t){// 找到了
        for(int i=1;i<deep;i++)
            cout<<way[i]<<' ';
        cout<<'\n';
        exit(0);
    }
    cnt[u]=1;
    for(auto [c,v]:edge[u])
        if(is_exper[v]){
            way[deep]=c;
            dfs(v,deep+1);
        }
}
signed main(){
    cin>>n>>m>>s>>t;
    for(int i=1,u,v,c;i<=m;i++){
        cin>>u>>v>>c;
        edge[u].pb(mp(c,v));
        not_edge[v].pb(u);// 反向图不用存价值（因为没用）
    }
    for(int i=1;i<=n;i++)
        sort(edge[i].bg(),edge[i].ed());
    can(t);
    if(!is_exper[s]){// 达不到
        cout<<"IMPOSSIBLE\n";
        return 0;
    }
    dfs(s,1);
    你不可以 copy 题解哦！
    return 0;
}

:::