uva 10986 Sending email (spfa)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年05月25日 星期三 03时25分27秒
  4File Name :code/uva/10986.cpp
  5************************************************ */
  6
  7#include <cstdio>
  8#include <cstring>
  9#include <iostream>
 10#include <algorithm>
 11#include <vector>
 12#include <queue>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <ctime>
 19#define fst first
 20#define sec second
 21#define lson l,m,rt<<1
 22#define rson m+1,r,rt<<1|1
 23#define ms(a,x) memset(a,x,sizeof(a))
 24typedef long long LL;
 25#define pi pair < int ,int >
 26#define MP make_pair
 27
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=2E4+7;
 34int n,m;
 35int S,T;
 36vector < pi > edge[N];
 37
 38int d[N];
 39bool inq[N];
 40bool spfa( int s,int t)
 41{
 42    ms(d,0x3f);
 43    ms(inq,false);
 44    queue<int>q;
 45    q.push(s);
 46    inq[s] = true;
 47    d[s] = 0;
 48
 49    while (!q.empty())
 50    {
 51	int u = q.front();
 52	q.pop();
 53	inq[u] = false;
 54
 55	int siz = edge[u].size();
 56
 57	for ( int i = 0 ; i < siz ; i++)
 58	{
 59	    int v = edge[u][i].fst;
 60	    if (d[v]>d[u] + edge[u][i].sec)
 61	    {
 62		d[v] = d[u] + edge[u][i].sec;
 63		if (inq[v]) continue;
 64		inq[v] = true;
 65		q.push(v);
 66	    }
 67	}
 68    }
 69    return d[t]!=inf;
 70}
 71int main()
 72{
 73	#ifndef  ONLINE_JUDGE 
 74	freopen("code/in.txt","r",stdin);
 75  #endif
 76	ios::sync_with_stdio(false);
 77	int TT;
 78	cin>>TT;
 79	int cas = 0 ;
 80	while (TT--)
 81	{
 82	    cin>>n>>m>>S>>T;
 83	    for ( int i = 0 ; i <= n ; i++) edge[i].clear();
 84	    for ( int i = 1 ; i <= m ; i++)
 85	    {
 86		int u,v,w;
 87		cin>>u>>v>>w;
 88		edge[u].push_back(make_pair(v,w));
 89		edge[v].push_back(make_pair(u,w));
 90	    }
 91
 92	    if (spfa(S,T))
 93	    {
 94		printf("Case #%d: %d\n",++cas,d[T]);
 95	    }
 96	    else
 97	    {
 98		printf("Case #%d: unreachable\n",++cas);
 99	    }
100
101	}
102
103  #ifndef ONLINE_JUDGE  
104  fclose(stdin);
105  #endif
106    return 0;
107}