UVA 1599 - Ideal Path

//Bismillahir Rahman-ir Rahim
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout << '>' << #x << " : " << x << endl;
#define all(c) c.begin(), c.end()
#define F first
#define S second
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef unsigned long long ull;
typedef long long ll;

const ll mx = 1e5+7;

vector < ll > adj[mx];
map < pair < ll, ll >, ll > cost;

vector <ll> levels(mx);
vector <ll> vis(mx);
vector <ll > level(mx);
vector < ll > mn(mx, LLONG_MAX);

void bfs(ll source, ll n){

    vis.assign(n+10, 0);
    level.assign(n+10, 0);
    vis[source] = 1;
    queue < ll > q;
    q.push(source);
    while(!q.empty()){
        ll u = q.front();
        q.pop();

        for(auto v: adj[u]){
            if(!vis[v]){
                vis[v] = 1;
                level[v] = level[u]+1;
                q.push(v);
            }
        }
    }
}

void bfsA(ll source){

    queue < ll > q;
    q.push(source);

    while(!q.empty()){
        ll u = q.front();
        q.pop();

        // find min cost of active nodes in each level

        for(auto v: adj[u]){

            // if this node is not deleted and this node is on the next level of current node's level, and it's cost is not zero,
            // then I'll find its cost and compare it to all the cost in the next level
            if(!vis[v] && (levels[v] == levels[u]+1) && cost[{min(u, v), max(u, v)}] != 0){
                mn[levels[v]] =  min(mn[levels[v]], cost[{min(u, v), max(u, v)}]);
            }
        }



        for(auto v: adj[u]){
            // if any node's cost is minimum, then I'll take it for checking
            if(!vis[v] && (levels[v] == levels[u]+1) && cost[{min(u, v), max(u, v)}] == mn[levels[v]]){
                q.push(v);
            }
        }

    }

}


int main(){


    ll n, m;
    cin >> n >> m;

    for(ll i  = 0; i < m; i++){
        ll u, v, c;
        cin >> u >> v >> c;

        adj[u].push_back(v);
        adj[v].push_back(u);

        // taking the minimum cost between two nodes

        if(cost[{min(u, v), max(u, v)}] != 0) cost[{min(u, v), max(u, v)}] = min(c, cost[{min(u, v), max(u, v)}]);
        else cost[{min(u, v), max(u, v)}] = c;
    }


    bfs(1, n);

    for(ll i = 1; i <= n; i++){
        levels[i] = level[i]; // levels is level from source
    }

    bfs(n, n);




    // deleting unnecessary nodes by making it visited
    vis.assign(n+10, 0);
    for(ll i = 2; i < n; i++){
        if(levels[i] + level[i] != levels[n]){
            // delete i'th node
            vis[i] = 1;
        }
    }

    bfsA(1);

    cout << levels[n] << endl;

    for(ll i = 1; i <= levels[n]; i++){
        cout << mn[i];
        if(i != levels[n]){
            cout << ' ';
        }
    }
    cout << '\n';

    return 0;
}