[UVA][SSSP] 10986 - Sending email
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." |
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 |
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#define oo 1000000000
using namespace std;
typedef struct {
int to, v;
} Arc;
vector<Arc> myLink[20000];
void SPFA(int n, int st, int ed) {
bool used[n];
int dis[n];
memset(used, 0, sizeof(used));
for(int i = 0; i < n; i++)
dis[i] = oo;
queue<int> Q;
Q.push(st);
dis[st] = 0;
int tv;
while(!Q.empty()) {
tv = Q.front();
Q.pop();
used[tv] = 0;
for(vector<Arc>::iterator i = myLink[tv].begin(); i != myLink[tv].end(); i++) {
if(dis[i->to] > dis[tv] + i->v) {
dis[i->to] = dis[tv] + i->v;
if(!used[i->to]) {
used[i->to] = true;
Q.push(i->to);
}
}
}
}
if(dis[ed] == oo)
puts("unreachable");
else
printf("%d\n", dis[ed]);
}
int main() {
int N, Case = 0, i;
int x, y, w, n, m, S, T;
scanf("%d", &N);
while(N--) {
scanf("%d %d %d %d", &n, &m, &S, &T);
for(i = 0; i < n; i++) {
myLink[i].clear();
}
Arc tmp;
while(m--) {
scanf("%d %d %d", &x, &y, &tmp.v);
tmp.to = y;
myLink[x].push_back(tmp);
tmp.to = x;
myLink[y].push_back(tmp);
}
printf("Case #%d: ", ++Case);
SPFA(n, S, T);
}
return 0;
}