题解：AT_abc417_e A Path in A Dictionary

yszkddzyh · 2025-08-02 23:06:31 · 题解

考虑 dfs，从每一个点走到它下一个点时，要按照点的编号从小到大地走，以保证当我们第一次遍历到终点的时候，得到的路径一定是字典序最小的。

代码注释较详细。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e3 + 5;
int T, n, m, s, t, tot, ans[N];

bool vis[N], f;
vector <int> G[N];
// tot 是最后记录路径长度
// ans 是用来记录路径的
// vis 是当前点是否访问过
// f 是 dfs 中标记终点是否已经走到过

void dfs(int u, int st){
    // st 是当前遍历到的点 u 在路径中的位置
    vis[u] = 1;
    ans[st] = u;
    if(u == t){
        tot = st;
        // 因为我是在主函数中输出，所以需要令开一个 tot 记录路径长度
        // 你可以在这里直接输出，这就不需要 tot 这个变量了
        f = 1; // 标记终点已经访问过
        return;
    }
    for(int v : G[u]){
        if(vis[v]) continue; // 题目要求路径上不能有重复的点
        dfs(v, st + 1);
        if(f) return;
        // 如果已经访问过终点，就已经找到答案，那么就不用继续 dfs 了
    }
}

int main(){

    ios :: sync_with_stdio(false);
    cin >> T;
    while(T--){
        cin >> n >> m >> s >> t;
        for(int i = 1, u, v; i <= m; i++)
            cin >> u >> v, G[u].emplace_back(v), G[v].emplace_back(u);
        for(int i = 1; i <= n; i++)
            sort(G[i].begin(), G[i].end()); // 排序以满足字典序要求
        f = 0;
        dfs(s, 1);
        for(int i = 1; i <= tot; i++) cout << ans[i] << ' ';
        cout << '\n';
        for(int i = 1; i <= n; i++) G[i].clear(), vis[i] = 0; // 多测清空
    }

    return 0;
}