LightOj 1002 Country Roads Solution

 

Problem Link : https://lightoj.com/problem/country-roads

Solution in C++:

/// La ilaha illellahu muhammadur rasulullah

///******Bismillahir-Rahmalenir-Rahim******///

/// Abul Haslenat  Tolenmoy

/// Departmelent of CSE,23rd batch

/// Islamic Uleniversity,Balengladesh

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

#include <bits/stdc++.h>

using namespace std ;

#define mx 1009

#define inf 20009

std::vector<int> adj[mx],cost[mx];

int dis[mx] , n , v;

struct node{

    int u, w;

    node(int a, int b){

        u=a, w=b;

    }

    bool operator < (const node & p)const{

        return p.w<w;

    }

};

void dijstra ( int  source){

  priority_queue<node>q ;

  for ( int i = 0 ; i < n ; i++ ) {

    dis[i] = inf ;

  }

  dis[source] = 0 ;

  q.push(node(source,0)) ;

  while (!q.empty()) {

    node  top  = q.top() ;

    q.pop() ;

    int u = top.u ;

    for ( int i = 0 ; i < adj [u].size() ; i++ ) {

       int v = adj[u][i] ;

       int temp = max ( dis[u] , cost [u][i]) ;

       if ( temp < dis[v]){

        dis[v] = temp ;

        q.push(node(v,dis[v]));

       }

    }

  }

}

int main()

{

    int t,cs=1;

    cin>>t;

    while(t--){ 

       for(int i=0; i<n; i++)

        {

            adj[i].clear();

            cost[i].clear();

        }

        int e,u,v,w,m ;

        cin>>n>>e;

        while(e--)

        {

            cin>>u>>v>>w;

            adj[u].push_back(v);

            adj[v].push_back(u);

            cost[u].push_back(w);

            cost[v].push_back(w);

        }

        int source ;

        cin>>source;

        dijstra(source);

        cout<<"Case "<<cs++<<":"<<endl;

        for(int i=0; i<n; i++)

        {

            if(dis[i]==inf)

                cout<<"Impossible"<<endl;

            else

                cout<<dis[i]<<endl;

        }

       

    }

    return 0;

}