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

· · 题解

很高兴找到一个可以写题解的题！QAQ

核心思路

  1. 可达性预处理：反向图 BFS 标记所有能到达终点 T 的节点，仅保留这些节点构成的有效子图（无效路径直接排除）。

  2. 贪心选边：从起点 S 出发，每步选择当前节点出边中「颜色最小」且「终点在有效子图内」的边，保证字典序最优。

  3. 环与长度检测：若路径中出现重复节点（环），则序列可无限长（输出 TOO LONG）；若序列长度超 10^6，同样输出 TOO LONG。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXL = 1e6;
vector<vector<pair<int, int>>> f_adj(MAXN);
vector<vector<int>> r_adj(MAXN);
vector<bool> rech(MAXN, false);
vector<bool> in_p(MAXN, false);
vector<int> res;
int main(){
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        f_adj[u].emplace_back(v, c);
        r_adj[v].push_back(u);
    }
    queue<int> q;
    q.push(t);
    rech[t] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : r_adj[u]) {
            if (!rech[v]) {
                rech[v] = true;
                q.push(v);
            }
        }
    }
    if (!rech[s]) {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    int curr = s;
    while (true) {
        if (curr == t) {
            if (res.size() <= MAXL) {
                for (size_t i = 0; i < res.size(); ++i) {
                    if (i) cout << " ";
                    cout << res[i];
                }
                cout << endl;
            } else {
                cout << "TOO LONG" << endl;
            }
            return 0;
        }
        if (in_p[curr]) {
            cout << "TOO LONG" << endl;
            return 0;
        }
        in_p[curr] = true;
        int min_c = INT_MAX;
        int next_n = -1;
        for (auto &[v, c] : f_adj[curr]) {
            if (rech[v] && c < min_c) {
                min_c = c;
                next_n = v;
            }
        }
        if (next_n == -1) {
            cout << "IMPOSSIBLE" << endl;
            return 0;
        }
        res.push_back(min_c);
        if (res.size() > MAXL) {
            cout << "TOO LONG" << endl;
            return 0;
        }
        curr = next_n;
    }
    return 0;
}

The end.