1002 - Country Roads

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1002

Solution :

#include<bits/stdc++.h>
#define inf 100000

using namespace std;

vector<int> v[600],cost[600];

int dis[600];


struct node
{
    int city,dist;

    node(int a,int b)
    {
        city=a;
        dist=b;
    }

    bool operator <(const node &p)const
    {
        return p.dist<dist;
    }
};

void dijkstra(int s)
{

    for(int i=0;i<600;i++) dis[i]=inf;

    dis[s]=0;

    priority_queue<node>q;

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

    while(!q.empty())
    {

       node t=q.top();
        q.pop();

        int u=t.city;

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

            if(dis[p]>max(dis[u],cost[u][i]))
            {
                dis[p]=min(dis[p],max(dis[u],cost[u][i]));
                q.push(node(p,dis[p]));

            }
        }
    }

}

int main()
{



    int n,e,t,a,b,c,s;
    scanf("%d",&t);

for(int ca=1;ca<=t;ca++)

  {

scanf("%d%d",&n,&e);


    for(int i=1;i<=e;i++)
    {
        scanf("%d%d%d",&a,&b,&c);

        v[a].push_back(b);
        v[b].push_back(a);
        cost[a].push_back(c);
        cost[b].push_back(c);
    }

    scanf("%d",&s);



    dijkstra(s);

    printf("Case %d:\n",ca);

    for(int i=0;i<n;i++)
    {
        if(dis[i]==inf) printf("Impossible\n");
        else printf("%d\n",dis[i]);
    }

    for(int i=0;i<600;i++)
    {
        v[i].clear();
        cost[i].clear();
    }

  }

}