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

· · 题解

闲话

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

正文

第一眼感觉非常恐怖啊，先是要求字典序最小，又定义了字典序，长的一匹。

但是认真看了一下数据范围，又看了看题目要求，一眼就发现这本质上就是一个带剪枝优化的深搜。

要求字典序最小，那我们就对邻接表从小到大排序，这样可以保证每次访问的点一定是最小的。因为你要是之前的点合法，就不会访问到这里，所以这里就优化了很大一部分时间。

最后记录一下每个点的前驱，存到数组里再倒序输出就可以了。

代码

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