Codeforces Alpha Round #20 (Codeforces format) 20C. Dijkstra? Solution

  

 

Problem Link:  https://codeforces.com/contest/20/problem/C

Solution in C++:

///La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmanir-Rahim******///

///Abul Hasnat  Tonmoy

///Department of CSE,23rd batch

///Islamic University,Bangladesh

///**********ALLAH IS ALMIGHTY************///

#include<bits/stdc++.h>

using namespace std;

#define inf 1e15

long long n,m,u,v,w,i,j,dis[100009],node[100009];

map<int,vector<pair<int,int>>>g;

priority_queue<int>q;

void print(int n)

{

    if(n!=1)

        print(node[n]);

        cout<<n<<" ";

}

int main()

{

    cin>>n>>m;

    while(m--)

    {

        cin>>u>>v>>w;

        g[u].push_back({v,w});

        g[v].push_back({u,w});

    }

    for(i=1;i<=n;i++)

    {

        node[i]=i;

        dis[i]=inf;

    }

    q.push(1);

    dis[1]=0;

    while(!q.empty())

    {

        u=q.top();

        q.pop();

        for(i=0;i<g[u].size();i++)

        {

            v=g[u][i].first;

            w=g[u][i].second;

            if(dis[u]+w<dis[v])

            {

                dis[v]=dis[u]+w;

                node[v]=u;

                q.push(v);

            }

        }

    }

    if(dis[n]==inf)

        cout<<"-1"<<endl;

    else

    {

        print(n);

        cout<<endl;

    }

}