UVa 10986 - Sending Email

//aarifshuvo  ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

#define inf 999999999
#define MX 20007

vector<int> adj[MX];
vector<ll> cost[MX];
ll n,e,u,v,x,y,z;
bool mark[MX];
ll d[MX];
int par[MX];

struct node
{
    int city , cst;

    node(int _city, int _cst)
    {
        city = _city;
        cst = _cst;
    }

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

void dijkstra(int src)
{
    REP(i,MX) d[i] = inf;

    priority_queue <node> pq;

    pq.push(node(src,0));   d[src] = 0;

    while(!pq.empty())
    {
        node x = pq.top();   pq.pop();

        int u = x.city;   mark[u] = 1;

        REP(i,SZ(adj[u]))
        {
            int v = adj[u][i];
            int cst = cost[u][i];

            if(mark[v]==1) continue;

            if(cst+d[u] < d[v])  d[v] = cst+d[u],  pq.push(node(v,d[v]));
        }
    }

}

int main()
{
    ll t,src,dest;
    scl(t);
    FOR(cs,1,t)
    {
        scll(n,e);
        scll(src,dest);

        REP(i,e)
        {
            scll(x,y), scl(z);
            adj[x].push_back(y);
            adj[y].push_back(x);
            cost[x].push_back(z);
            cost[y].push_back(z);
        }

        dijkstra(src);

        if(d[dest]==inf) printf("Case #%d: unreachable\n", cs);
        else printf("Case #%d: %lld\n", cs, d[dest]);

        memset(mark, 0 , sizeof mark);
        REP(i,MX) adj[i].clear(), cost[i].clear();
    }

    return 0;
}

/*
3
3 3 2 0
0 1 100
0 2 200
1 2 50
*/