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

zhangshiyan · 2025-12-04 16:40:00 · 题解

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

思路

手模样例发现可能出现 TOO LONG 的情况下，会在一个字典序最小的环中出现。

一个很自然的思路：反向 BFS 标记所有能到达终点 T 的节点，以保证不经过无效路径。

从起点 S 出发，每步选择当前节点出边中，颜色最小的点，保证字典序最小。若路径中出现重复节点，则序列可无限长。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const ll N = 1e5;

ll n, m, s, t;
vector<pair<ll, ll>> g[N + 5];
vector<ll> rg[N + 5];
vector<ll> ans;

bool vis[N + 5], vis1[N + 5];

bool cmp(pair<ll, ll> a, pair<ll, ll> b)
{
    return a.second < b.second;
}

void dfs(ll u)
{
    vis[u] = 1;
    for (ll v : rg[u])
    {
        if (!vis[v])
        {
            dfs(v);
        }
    }
}

void dfs1(ll u)
{
    if (vis1[u])
    {
        cout << "TOO LONG" << endl;
        exit(0);
    }
    vis1[u] = 1;
    if (u == t)
    {
        for (ll i : ans)
        {
            cout << i << " ";
        }
        cout << endl;
        exit(0);
    }
    for (pair<ll, ll> p : g[u])
    {
        if (vis[p.first])
        {
            ans.push_back(p.second);
            dfs1(p.first);
//          ans.pop_back();
        }
    }
}

int main()
{
    n = read(), m = read(), s = read(), t = read();
    for (ll i = 1; i <= m; i++)
    {
        ll u = read(), v = read(), c = read();
        g[u].push_back(make_pair(v, c));
        rg[v].push_back(u);
    }
    for (ll i = 1; i <= n; i++)
    {
        sort(g[i].begin(), g[i].end(), cmp);
    }
    dfs(t);
    if (!vis[s])
    {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }
    dfs1(s);
    return 0;
}