首页 > 代码库 > UVA 10986 Sending email(SPFA)

UVA 10986 Sending email(SPFA)

There are n SMTP servers connected by network cables. Each of the m cables connects two computers and has a certain latency measured in milliseconds required to send an email message. What is the shortest time required to send a message from server S to server T along a sequence of cables? Assume that there is no delay incurred at any of the servers.

Input
The first line of input gives the number of cases, NN test cases follow. Each one starts with a line containing n (2<=n<20000), m (0<=m<50000), S (0<=S<n) and T (0<=T<n). S!=T. The next m lines will each contain 3 integers: 2 different servers (in the range [0, n-1]) that are connected by a bidirectional cable and the latency, w, along this cable (0<=w<=10000).

Output
For each test case, output the line "Case #x:" followed by the number of milliseconds required to send a message from S to T. Print "unreachable" if there is no route from S to T.

Sample InputSample Output
3
2 1 0 1
0 1 100
3 3 2 0
0 1 100
0 2 200
1 2 50
2 0 0 1
Case #1: 100
Case #2: 150
Case #3: unreachable



最短路问题,拿SPFA练手。

题意:从起点S发送信息到终点T的最短路。直接上SPFA了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=20020*5;//RE几次,记得开大点
int head[maxn],end[maxn],cost[maxn];
int next[maxn],d[maxn],cnt[maxn];
int visit[maxn];
int t,n,m,e;
int S,T;
void add(int u,int v,int w)//邻接表
{
    end[e]=v;
    cost[e]=w;
    next[e]=head[u];
    head[u]=e++;
}
void  SPFA(int x)//SPFA
{
    memset(cnt,0,sizeof(cnt));
    memset(visit,0,sizeof(visit));
    memset(d,INF,sizeof(d));
    queue<int>q;
    q.push(x);
    visit[x]=1;
    cnt[x]++;
    d[x]=0;
    q.push(x);
    while(!q.empty())
    {
        int uu=q.front();
//        cout<<q.front()<<endl;
        q.pop();
        visit[uu]=0;
        for(int i=head[uu];i!=-1;i=next[i])
        {
            int vv=end[i];
            int ww=cost[i];
            if(d[vv]>d[uu]+ww)
            {
                d[vv]=d[uu]+ww;
                if(!visit[vv])
                {
                    visit[vv]=1;
                    q.push(vv);
                    if(++cnt[vv]>n)
                        return ;
                }
            }
        }
    }
}
int main()
{
    int u,v,w;
    int cas=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&n,&m,&S,&T);
        e=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);//无向图
            add(v,u,w);
        }
        SPFA(S);
//        cout<<cost[0]<<"  "<<cost[1]<<endl;
//       cout<<d[0]<<" "<<d[T]<<endl;
        if(d[T]<INF)  printf("Case #%d: %d\n",++cas,d[T]);
        else  printf("Case #%d: unreachable\n",++cas);
    }
    return 0;
}