uva 10986 - Sending email

1思路： SPFA + 無向圖鄰接表
2分析：
   1題目給定的n最大20000，m最大50000，分析復雜度後發現只有SPFA最靠譜。
   2分析題目的樣列可知，這一題是要用鄰接矩陣來存儲無向圖，所以要注意無向圖怎麼存儲在鄰階表中
   2連接表的橫列有N項，縱列也是N項。形成的N*N項每項都被稱為邊結點，每項都有縱橫兩個坐標，例如點（N,N-1），表示的就是從第N點向第N-1點有無路徑。由於有E條邊，自然有E條路徑，但是由於無向=雙向，所以要乘以2
3代碼：

[cpp] 
#include<iostream> 
#include<algorithm> 
#include<cstdio> 
#include<cstring> 
#include<queue> 
using namespace std; 
#define INF 0xFFFFFFF 
#define MAXN 100010/*存儲無向圖的時候乘以2*/ 
 
int T , n , m , s , t; 
int first[MAXN] , next[MAXN]; 
int star[MAXN] , end[MAXN] , value[MAXN]; 
int dis[MAXN]; 
queue<int>q; 
 
void init(){ 
     while(!q.empty()) 
        q.pop(); 
     memset(first , -1 , sizeof(first)); 
     memset(next , -1 , sizeof(next)); 
     for(int i = 0 ; i < n ; i++){ 
        if(i == s) 
          dis[i] = 0; 
        else 
          dis[i] = INF; 
     } 
} 
 
void SPFA(){ 
     int vis[MAXN]; 
     memset(vis , 0 , sizeof(vis));  
     q.push(s); 
     while(!q.empty()){      
         int tmp = q.front();        
         q.pop(); 
         vis[tmp] = 0; 
         printf("%d\n" , first[tmp]); 
         for(int i = first[tmp] ; i !=-1 ; i = next[i]){ 
            if(dis[end[i]] > dis[tmp] + value[i]){ 
               dis[end[i]] = dis[tmp] + value[i]; 
               if(!vis[end[i]]){ 
                  vis[end[i]] = 1; 
                  q.push(end[i]); 
               } 
            } 
         }         
     } 
} 
 
int main(){ 
    //freopen("input.txt" , "r" , stdin); 
    int cnt = 1; 
    scanf("%d" , &T); 
    while(T--){ 
       scanf("%d%d%d%d" , &n , &m , &s , &t); 
       init(); 
       for(int i = 0 ; i < m ; i++){ 
          scanf("%d%d%d" , &star[i] , &end[i] , &value[i]); 
          star[i+m] = end[i];。/*這裡要注意*/ 
          end[i+m] = star[i]; /*這裡要注意*/ 
          value[i+m] = value[i]; 
 
          next[i] = first[star[i]]; 
          first[star[i]] = i; 
          next[i+m] = first[star[i+m]]; 
          first[star[i+m]] = i+m; 
       } 
       SPFA(); 
       if(!m || dis[t] == INF) 
         printf("Case #%d: unreachable\n" , cnt++); 
       else 
         printf("Case #%d: %d\n" , cnt++ , dis[t]); 
    } 
    return 0; 
}