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

#include <bits/stdc++.h>

#define int long long
#define endl "\n"

using namespace std;

namespace zcq_qwq {
    const int N = 1000 + 5, M = 50000 + 5;

    int h[N], to[M << 1], nxt[M << 1];

    vector<int> d[N];

    bool vis[N];

    int t, n, m, tot, s, ed;

    void add(int a, int b) {
        to[tot] = b;
        nxt[tot] = h[a];
        h[a] = tot++;
    }

    struct node {
        vector<int> f;

        int u;

        bool operator < (const node & x) const {
            return f > x.f;
        }
    };

    void dijkstra(int st) {
        for (int i = 1; i <= n; i++) {
            d[i] = {0x3f3f3f3f};
        }
        memset(vis, 0, sizeof vis);
        priority_queue<node> pq;
        d[st] = {st};
        pq.push({d[st], st});
        while (!pq.empty()) {
            node u = pq.top();
            pq.pop();
            if (vis[u.u]) continue;
            vis[u.u] = true;
            for (int i = h[u.u]; ~i; i = nxt[i]) {
                int j = to[i];
                vector<int> vec;
                vec = d[u.u];
                vec.push_back(j);
                if (d[j] > vec) {
                    d[j] = vec;
                    pq.push({d[j], j});
                }
            }
        }
    }

    void solve() {
        memset(h, -1, sizeof h);
        memset(to, 0, sizeof to);
        memset(nxt, 0, sizeof nxt);
        tot = 0;
        cin >> n >> m >> s >> ed;
        for (int i = 1; i <= m; i++) {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
        dijkstra(s);
        for (auto i : d[ed]) {
            cout << i << " ";
        }
        cout << endl;
    }

    void main() {
        cin >> t;
        while (t--) {
            solve();
        }
    }
}

signed main() {
    zcq_qwq::main();
    return 0;
}