专栏文章

题解：AT_abc417_e [ABC417E] A Path in A Dictionary

lliangjiande
AT_abc417_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2pbqb
此快照首次捕获于
2025/12/01 19:35
3 个月前
此快照最后确认于
2025/12/01 19:35
3 个月前
查看原文

闲话

话说这个题怎么这么简单，这真的是倒数第三道吗？

正文

第一眼感觉非常恐怖啊，先是要求字典序最小，又定义了字典序，长的一匹。
但是认真看了一下数据范围，又看了看题目要求，一眼就发现这本质上就是一个带剪枝优化的深搜。
要求字典序最小，那我们就对邻接表从小到大排序，这样可以保证每次访问的点一定是最小的。因为你要是之前的点合法，就不会访问到这里，所以这里就优化了很大一部分时间。
最后记录一下每个点的前驱，存到数组里再倒序输出就可以了。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--){
		int n,m,st,ed;cin>>n>>m>>st>>ed;
		V<V<int> >e(n+1);
		FOR(i,1,m){
			int u,v;cin>>u>>v;
			e[u].pb(v);
			e[v].pb(u);
		}
		FOR(i,1,n) sort(e[i].begin(),e[i].end());
		V<int>pre(n+1,-1);
		V<bool>vis(n+1,false);
		function<bool(int,int)>dfs=[&](int u,int fa){
			if(u==ed) return true;
			vis[u]=true;
			for(int v:e[u]){
				if(vis[v])continue;
				pre[v]=u;
				if(dfs(v,u)) return true;
			}
			return false;
		};
		dfs(st,0);
		V<int>ans;
		for(int u=ed;u!=-1;u=pre[u])ans.pb(u);
		reverse(ans.begin(),ans.end());
		for(int i:ans) cout<<i<<" ";
		cout<<"\n"; 
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...