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

Lysra · 2025-11-28 07:17:11 · 题解

Solution

接触过一个加强版，区别在于本题保证边权两两不同。

首先字典序最小肯定是满足贪心的，每一步尽可能往小走。

其次你要保证你走的地方最终存在一条路径到达 T 点。

所以先建反图把所有 T 点能够到达的地方跑出来，然后再去原图上做贪心。

如果 T 无法到达 S 就是 IMPOSSIBLE，如果贪心的时候走到了之前走过的点就是 TOO LONG。

Code

#include<bits/stdc++.h>
#define int long long
#define INF 1e18
#define N 1000005
using namespace std;
struct star{
    int next,to,v1,v2;
}e[N];
int n,m,s,t,head[N],cnt,vis[N],vv[N],a[N],tot;
void add(int u,int v,int w1,int w2){
    e[++cnt].next=head[u];
    head[u]=cnt,e[cnt].to=v;
    e[cnt].v1=w1,e[cnt].v2=w2;
}
void dfs(int x){
    vis[x]=1;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to,d=e[i].v2;
        if(!d||vis[y]) continue;
        dfs(y);
    }
}
void dfs1(int x){
    if(x==t){
        for(int i=1;i<=tot;i++) cout<<a[i]<<" ";
        exit(0);
    }
    if(vv[x]){
        cout<<"TOO LONG"; exit(0);
    }
    vv[x]=1; int qwq=INF,id;
    for(int i=head[x];i;i=e[i].next){
        int y=e[i].to,d1=e[i].v1,d2=e[i].v2;
        if(d2||!vis[y]) continue;
        if(d1<qwq) qwq=d1,id=y;
    }
    a[++tot]=qwq,dfs1(id);
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>s>>t;
    for(int i=1,u,v,w;i<=m;i++)
        cin>>u>>v>>w,add(u,v,w,0),add(v,u,w,1);
    dfs(t);
    if(!vis[s]){
        cout<<"IMPOSSIBLE";
        return 0;
    }
    dfs1(s);
    return 0;
}