UVa10986_Sending email(最短)(白皮书图论的话题)

时间:2022-10-04 06:18:03

解决报告

思路:

裸裸的最短路。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define inf 0x3f3f3f3f
#define N 40000
#define M 100000
using namespace std;
struct node
{
int v,w,next;
}edge[M];
int head[N],dis[N],vis[N],cnt,n,m,s,t;
void add(int u,int v,int w)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void spfa()
{
for(int i=0;i<n;i++)
{
dis[i]=inf;
vis[i]=0;
}
dis[s]=0;
vis[s]=1;
queue<int >Q;
Q.push(s);
while(!Q.empty()){
int u=Q.front();
Q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
if(!vis[v])
{
vis[v]=1;
Q.push(v);
}
}
}
}
}
int main()
{
int i,j,T,u,v,w,k=1;
scanf("%d",&T);
while(T--)
{
memset(head,-1,sizeof(head));
cnt=0;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
spfa();
printf("Case #%d: ",k++);
if(dis[t]==inf)
printf("unreachable\n");
else printf("%d\n",dis[t]);
}
return 0;
}

Problem E

Sending email

Time Limit: 3 seconds

"A new internet watchdog is creating a stir in

Springfield. Mr. X, if that is his real name, has

come up with a sensational scoop."

Kent Brockman

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 toT. 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

Problemsetter: Igor Naverniouk

版权声明:本文博客原创文章。博客,未经同意,不得转载。