P14618 题解

copper_ingot · 2025-12-05 13:16:57 · 题解

题目传送门

简单图论题。

首先反向建边预处理出所有可以到达 t 的点，显然只有这些点和连接这些点的边才有意义。如果不能由 s 到达 t 就输出无解。

之后对于每个点，选取从它连出的权值最小的边来走。如果走到了已经经过的点，说明走到了一个极小权值的环里，如果一直在这个环上走字典序就最小，此时序列为无限长。

如果序列是有限的，那么每个点最多经过一次，序列最长为 n，不需要判断 10^6 的限制。

代码：

//copper_ingot
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
pii mkp(int x, int y){pii p; p.first = x, p.second = y; return p;}
int n, m, s, t, vis[200001], flag, a[200001], cnt;
vector<pii> g[200001], h[200001];
void dfs1(int u){
    vis[u] = 1;
    for (int i = 0; i < g[u].size(); i++)
        if (!vis[g[u][i].second]) dfs1(g[u][i].second);
}
void dfs2(int u){
    if (flag || u == t) return;
    if (vis[u]){flag = 1; return;}
    vis[u] = 1, a[++cnt] = h[u][0].first;
    dfs2(h[u][0].second);
}
signed main(){
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++){
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        g[v].push_back(mkp(w, u));
    }
    dfs1(t);
    if (!vis[s]){puts("IMPOSSIBLE"); return 0;}
    for (int u = 1; u <= n; u++){
        if (!vis[u]) continue;
        for (int i = 0; i < g[u].size(); i++){
            int v = g[u][i].second, w = g[u][i].first;
            if (!vis[v]) continue;
            h[v].push_back(mkp(w, u));
        }
    }
    for (int i = 1; i <= n; i++){sort(h[i].begin(), h[i].end()); vis[i] = 0;}
    dfs2(s);
    if (flag){puts("TOO LONG"); return 0;}
    for (int i = 1; i <= cnt; i++) printf("%d ", a[i]);
    return 0;
}