UVA 10986 - Sending email(cpp file)

Problem Type : Dijkstra



#include<bits/stdc++.h>
#define MAX 20001
#define INF 100000
using namespace std;
long int vertex,edge,source,des;
long int dist[MAX];
vector<long int>vcc[MAX],cost[MAX];
struct node
{
    long int x,c;
    node(long int d,long int f)
    {
        x=d;
        c=f;
    }
    bool operator<(const node &p)const
    {
        return c>p.c;
    }
};

void djkstra(long int s)
{
    priority_queue<node>Q;
    long  int ux,uy,vx,vy,i,j;
    dist[s]=0;
    Q.push(node(s,dist[s]));
    while(!Q.empty())
    {
        node top = Q.top();
        Q.pop();
        ux = top.x;
        for(i=0; i<vcc[ux].size(); i++)
        {
            long vx= vcc[ux][i];
            if(dist[vx]> dist[ux]+cost[ux][i])
            {
                dist[vx]=dist[ux]+cost[ux][i];
                Q.push(node(vx,dist[vx]));
            }

        }
    }
}
int main()
{
    long  int i,j,test,n,m,c,cas=0;
    scanf("%ld",&test);
    while(test--)
    {
        cas++;
        scanf("%ld %ld %ld %ld",&vertex,&edge,&source,&des);

        for(i=0; i<edge; i++)
        {
            scanf("%ld %ld %ld",&n,&m,&c);
            vcc[n].push_back(m);
            vcc[m].push_back(n);
            cost[m].push_back(c);
            cost[n].push_back(c);

        }
        for(i=0; i<vertex; i++)
        {
            dist[i]=INF;
        }
        djkstra(source);
        if(dist[des]==INF)
        {
            printf("Case #%ld: unreachable\n",cas);
        }
        else
        {
            printf("Case #%ld: %ld\n",cas,dist[des]);
        }
        for(i=0; i<MAX; i++)
        {
            vcc[i].clear();
        }
         for(i=0; i<MAX; i++)
        {
            cost[i].clear();
        }
    }

}