Single-Source Shortest Paths (Dijkstra)

#include <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <queue>

#include <climits>

using namespace std;

#define siz 1000005

#define INF INT_MAX

vector <int> vec[siz],cost[siz];

int d[siz];

int N,E;



struct data{

    int city,dist;

    bool operator < (const data &p) const{

        return dist > p.dist;

    }

};



int dijkstra(int source, int destination) {



    priority_queue<data> q;

    data u, v;

    u.city = source, u.dist = 0;

    q.push( u );

    d[ source ] = 0;



    while( !q.empty() ) {

        u = q.top(); q.pop();

        int ucost = d[ u.city ];



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

            v.city = vec[u.city][i], v.dist = cost[u.city][i] + ucost;

            if( d[v.city] > v.dist ) {

                d[v.city] = v.dist;

                q.push( v );

            }

        }

    }



    return d[ destination ];

}



void reset(){

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

        d[i]=INF;

        vec[i].clear();

        cost[i].clear();

    }

}

int main()

{

    int n,source,destination,u,v,c,k=1;

    //freopen("input.txt","r",stdin);

    scanf("%d",&n);

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

        scanf("%d%d%d%d",&N,&E,&source,&destination);

        reset();

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

            scanf("%d%d%d",&u,&v,&c);

            vec[u].push_back(v);

            vec[v].push_back(u);

            cost[u].push_back(c);

            cost[v].push_back(c);

        }



        dijkstra(source,destination);



        if(d[destination]==INF) printf("Case #%d: unreachable\n",k++);

        else printf("Case #%d: %d\n",k++,d[destination]);

    }

    return 0;

}