首页 > 代码库 > 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, N. N 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 Input | Sample 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; }