uva 10986 Sending email (spfa)
uva10986题目链接 题意：裸的spfa.
思路：模板，1A.
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}