uva 10986 - Sending email

点击打开链接uva 10986

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代码：

#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;
}