Untitled
// y.ha #include <bits/stdc++.h> #define cook '\n' #define maxn 100001 #define Task "B" #define F first #define S second using namespace std; int n,m,s,t,r=0; int tr[maxn]; bool ok = 0; vector<pair<int, int>> nxt[maxn]; void inp() { cin >> n >> m >> s >> t; while (m--) { int x, y, w; cin >> x >> y >> w; r = max(r, w); nxt[x].push_back({y, w}); nxt[y].push_back({x, w}); } } void dfs(int u, int h) { if (u == s) { ok = 1; return ; } for (auto x : nxt[u]) { if (h > x.S || tr[x.F]) continue; tr[x.F] = u; dfs(x.F,h) ; } } void write(int h) { dfs(t,h) ; vector<int> way(1,s) ; while ( s != t ) { way.push_back(tr[s]) ; s = tr[s] ; } cout << way.size() << cook ; for ( int x : way ) cout << x << " " ; } int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); if (fopen(Task ".INP", "r")) { freopen(Task ".INP", "r", stdin); freopen(Task ".OUT", "w", stdout); } inp(); int l = 0, ans = 0; while (l <= r) { memset(tr, 0, sizeof(tr)); ok = 0; int m = (r+l)/2; dfs(t,m) ; if (ok) ans = m, l = m + 1; else r = m - 1; } cout << ans << cook ; if ( ans ) write(ans) ; return 0; }
Leave a Comment