Untitled

 avatar
user_0483151
plain_text
a month ago
1.4 kB
2
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;
}
Leave a Comment