dijkstra.cpp

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define ll long long
#define vec vector
#define pii pair<int,int>
#define YES cout << "YES" << "\n"
#define NO cout << "NO" <<  "\n"

using namespace std;
const int MAXN = 2e5 + 5;
const ll INF = 1e18 + 7;
const ll MOD1 = 1e9 + 7;
const ll MOD2 = 1e9 + 9;
int a[MAXN];

vector <pair <int, int> > g[MAXN];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++){
        int x, y, cost;
        cin >> x >> y >> cost;
        g[x].pb({y, cost});
        g[y].pb({x, cost});
    }

    int s, f;
    cin >> s >> f;

    for (int i = 1; i <= n; i++){
        dist[i] = INF;
    }
    dist[s] = 0;
    pr[s] = -1;
    //O(n * n + m)
    for (int i = 1; i <= n; i++){
        minn = INF;
        v = -1;
        for (int j = 1; j <= n; j++){
            if (dist[j] < minn && !was[j]){
                minn = dist[j];
                v = j;
            }
        }
        if (minn == INF){
            break;
        }
        was[v] = 1;
        for (int j = 0; j < g[v].size(); j++){
            int to = g[v][j].f;
            int len = g[v][j].s;
            if (dist[to] > dist[v] + len){
                dist[to] = dist[v] + len;
                pr[to] = v;
            }
        }
    }
    if (dist[f] == INF){
        cout << -1;
    }
    else{
        cout << dist[f] << '\n';

        int x = f;
        vector <int> ans;
        while (x != -1){
            ans.pb(x);
            x = pr[x];
        }
        reverse(ans.begin(), ans.end());
        for (int v : ans){
            cout << v << ' ';
        }
    }


    // set O(mlogn)
     //      dist[v]  v
    set <pair <int, int> > st;

    for (int i = 1; i <= n; i++){
        dist[i] = INF;
    }
    dist[s] = 0;
    st.insert({dist[s], s});

    while (!st.empty()){
        pair <int, int> z = *st.begin();
        int v = z.s;

        for (int i = 0; i < g[v].size(); i++){
            int to = g[v][i].f;
            int len = g[v][i].s;

            if (dist[to] > dist[v] + len){
                st.erase({dist[to], to});
                dist[to] = dist[v] + len;
                st.insert({dist[to], to});
            }
        }
    }


    return 0;
}