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
#include
#include
#include
#include
#include
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
q; q.push(x); visit[x]=1; cnt[x]++; d[x]=0; q.push(x); while(!q.empty()) { int uu=q.front(); // cout<
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<