10986

Single source shortest path algorithm and priority_queue used to solve the problem.

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>

#define INF 1000000000
#define ll long long

using namespace std;
/*
struct node{
	int dest,weight;
};
*/
int n,m,src,dst;
vector<pair<int,int> > vb[20005];

void dijkstra(vector<ll> distance)
{
	int t_dist,t_node;
	int latency,v;
	pair<int,int> _intPair;
	priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > cue;
	cue.push(pair<int,int> (0,src));
	pair<int,int> tmp;
	while(!cue.empty())
	{
		tmp=cue.top();
		cue.pop();
		t_dist = tmp.first;
		t_node = tmp.second;

		if(t_dist==distance[t_node])//visited or discovered
		{
			for(int i=0;i<vb[t_node].size();i++)
			{
				_intPair = vb[t_node][i];
				v = _intPair.first;
				latency = _intPair.second;
				if(t_dist+latency<distance[v])
				{
					distance[v]=t_dist+latency;
					cue.push(make_pair(distance[v],v));
				}
			}
		}
	}

	if(distance[dst]!=INF)
		printf("%lld\n",distance[dst]);
	else
		printf("unreachable\n");
}

int main()
{
	int t;
	int kase=1;
	int s,d,wt;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d%d",&n,&m,&src,&dst);
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&s,&d,&wt);
			vb[s].push_back(make_pair(d,wt));
			vb[d].push_back(make_pair(s,wt));
		}
		vector<ll> distance(n,INF);
		distance[src]=0;
		printf("Case #%d: ",kase++);
		dijkstra(distance);
		for(int i=0;i<n;i++)
		vb[i].clear();
	}
	return 0;
}