UVA 10986 Sending email SPFA

题意：告诉n个点和m条边，求s到t的最短路径。

。

思路：N和M都比較大了。n有20000，m有50000。用邻接表加SPFA。

#include <iostream>
#include <stdio.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define INF 99999999
using namespace std;
int n,m,s,t;
int dis[22222];
int vis[22222];
int f[22222];
int nt[100009];
int u[100009],v[100009],w[100009];

void read_()
{
    memset(f,-1,sizeof f);
    for(int i=0;i<m*2;i+=2)
    {
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
        nt[i]=f[u[i]]; f[u[i]]=i;              //以u[i]开头的是第i个
        u[i+1]=v[i]; v[i+1]=u[i]; w[i+1]=w[i]; //无向图
        nt[i+1]=f[u[i+1]]; f[u[i+1]]=i+1;
    }
}

void SPFA()
{
    queue<int>q;
   for(int i=0;i<=n;i++)
   {
       vis[i]=0;dis[i]=INF;
   }

   dis[s]=0;
   q.push(s);

   while(!q.empty())
   {
       int x=q.front();q.pop();
       vis[x]=0;
       for(int i=f[x];i!=-1;i=nt[i])
           if(dis[x]+w[i]<dis[v[i]])
           {
               dis[v[i]]=dis[x]+w[i];
               if(vis[v[i]]==0)
               {
                   vis[v[i]]=1;
                   q.push(v[i]);
               }
           }
   }

    if(dis[t]==INF)
        puts("unreachable");
    else
        printf("%d
",dis[t]);
}

int main()
{
    int T;
    int a,b,c;
    scanf("%d",&T);
    for(int ca=1;ca<=T;ca++)
    {
        scanf("%d%d%d%d",&n,&m,&s,&t);

        read_();
        printf("Case #%d: ",ca);
        SPFA();
    }
    return 0;
}