20 C. Dijkstra? solution.

Problem Link: here 

solution:  Find Shortest path and print the path. 

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define MX 100005
vector <pii> adj[MX];
long long int dis[MX];
int prv[MX];

void Print(int n)
{
    if (n == 1) {
        cout<<1;
        return;
    }
    Print(prv[n]);
    cout<<" "<<n;

}
int main()
{
    int n,e;
    scanf("%d%d",&n,&e);
    int i;
    for (i=0;i<e;i++)
    {
        int u,v,cost;
        scanf("%d%d%d",&u,&v,&cost);
        adj[u].push_back(pii(cost,v));
        adj[v].push_back(pii(cost,u));
    }
    for (i=0;i<=n;i++) dis[i]=10000000000000,prv[i]=i;
    dis[1]=0;
    priority_queue <pii> pq;
    pq.push(pii(0,1));
    while(!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        for (i=0;i<adj[u].size();i++)
        {
            int v = adj[u][i].second;
            int w = adj[u][i].first;
            if (dis[v] > dis[u]+w)
            {
                dis[v] = dis[u]+w;
                prv[v] = u;
                pq.push(pii(-dis[v],v));
            }
        }
    }
    if (dis[n] == 10000000000000) {
        cout<<"-1"<<endl;
        return 0;
    }
    else Print(n);
    puts("");
    return 0;
}