Dijastra Algorithm

CF-20C.cpp

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
long long const inf = 1e13;
 
vector< int > g[100009];
vector< int > cost[100009];
 
int main()
{
    int n, m, tmp1, tmp2, wt, cst;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        cin >> tmp1 >> tmp2 >> wt;
        g[tmp1].push_back(tmp2),
        g[tmp2].push_back(tmp1),
        cost[tmp1].push_back(wt),
        cost[tmp2].push_back(wt);
    }
 
    long long dis[100009];
    fill(dis, dis + n + 2, inf);
    int par[100009];
 
    priority_queue< pair< int, int >, vector< pair< int, int > >, greater< pair<int, int> > > pq;
 
    pq.push( {0, 1} ), par[1] = 0, dis[1] = 0;
 
    while ( !pq.empty() )
    {
        pair< int, int > curTop = pq.top(); pq.pop();
        int parTemp = curTop.second;
        for(int i = 0; i < g[ parTemp ].size(); i++) {
            int curNode = g[ parTemp ][ i ]; 
            // cout << dis[curNode] << ' ' << cost[parTemp][i] << ' ' << dis[parTemp] << "*\n";
            if( dis[ curNode ] > cost[ parTemp ][i] + dis[ parTemp ] )
                dis[curNode] = cost[ parTemp ][i] + dis[ parTemp ],
                par[curNode] = parTemp,
                pq.push( { dis[ curNode ], curNode } ); 
        }
    }
 
    if(par[n] == 0){
        cout << "-1\n";
        return 0;
    }
 
    vector< int > path;
 
    while (par[n] != 0)
    {
        // cout << n << ' ';
        path.push_back(n);
        n = par[n];
    }
    path.push_back(n);
    
    reverse(path.begin(), path.end());
 
    for(int x: path)
        cout << x << ' ';
 
    cout << '\n';
 
    return 0;
}