10986 - Sending email

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#define INFINITY 100100
#define MAX 20005
using namespace std;

long int test,n,m,S,T,ucost,i,x,w,a,b,len;

vector<long int>G[MAX],cost[MAX];

long int dist[MAX];

struct data
{
    long int server,latency;
};

struct cmp
{
    bool operator()(data lhs,data rhs)
    {
        return lhs.latency<rhs.latency;
    }
};

void dijkstra(long int source,long int destination)
{
    for(i=0;i<=n;i++)
    {
        dist[i]= INFINITY;
    }
    priority_queue<data,vector<data>,cmp>Q;
    data u,v;
    u.server=source;
    u.latency=0;
    dist[source]=0;
    Q.push(u);
    while(!Q.empty())
    {
        u = Q.top();
        Q.pop();

        ucost = u.latency;

        len = G[u.server].size();

        for(i=0;i<len;i++)
        {
            v.server = G[u.server][i];
            v.latency = cost[u.server][i]+ucost;
            if(dist[v.server]>v.latency)
            {
                dist[v.server] = v.latency;
                Q.push(v);
            }
        }
    }
}

int main()
{
    cin>>test;
    for(x=1;x<=test;x++)
    {
        cin>>n>>m>>S>>T;
        for(i=0;i<m;i++)
        {
            cin>>a>>b>>w;
            G[a].push_back(b);
            G[b].push_back(a);
            cost[a].push_back(w);
            cost[b].push_back(w);
        }

        dijkstra(S,T);

        if(dist[T]!=INFINITY)
        {
            printf("Case #%ld: %ld\n",x,dist[T]);
        }
        else
        {
            printf("Case #%ld: unreachable\n",x);
        }

        for(i=0;i<n;i++)
        {
            G[i].clear();
            cost[i].clear();
        }
    }
    return 0;
}