Untitled
user_0483151
plain_text
10 months ago
1.4 kB
4
Indexable
// 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;
}
Editor is loading...
Leave a Comment