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

Solution

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

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

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

T

点。

所以先建反图把所有

T

点能够到达的地方跑出来，然后再去原图上做贪心。

如果

T

无法到达

S

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

Code

CPP

#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;
}

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

文章操作

Solution

Code

相关推荐

评论

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