UVa 10986 - Sending Email

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

伺服器由雙向的網路線相連,並有傳遞時間,請找出從起點伺服器到目的地的最短時間。

Solution

直接做 Dijkstra 找最短路徑即可。

Code

UVa 10986UVa 10986 - Sending Email
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#define N 20000
using namespace std;

struct Node
{
int v, w;
Node(){}
Node(int vv, int ww) :v(vv), w(ww){}
bool operator<(const Node& a)const{return w > a.w; }//小的優先
};
vector<Node>list[N];//adjacent list
int dijkstra(int s, int goal, int n);
int main()
{
int Case;
scanf("%d", &Case);
for (int c = 1; c <= Case; c++)
{
int n, m, s, t, u, v, w, i;
scanf("%d%d%d%d", &n, &m, &s, &t);
for (i = 0; i < n; i++)
list[i].clear();

for (int i = 0; i < m; i++)
{
scanf("%d%d%d", &u, &v, &w);
list[u].push_back(Node(v, w));
list[v].push_back(Node(u, w));
}

printf("Case #%d: ", c);
int ans = dijkstra(s, t, n);
if (ans == 1e9)
puts("unreachable");
else
printf("%d\n", ans);
}

return 0;
}
int dijkstra(int s, int goal, int n)
{
bool isVisit[N] = {};
int d[N];
fill(d, d + n, 1e9);

d[s] = 0;
priority_queue<Node> PQ;
PQ.push(Node(s, 0));

while (true)
{
int next = -1;
while (!PQ.empty() && isVisit[next = PQ.top().v])
PQ.pop();

if (next == -1 || next == goal)
return d[goal];
isVisit[next] = true;

for (Node node : list[next])
{
if (!isVisit[node.v] && d[next] + node.w < d[node.v])
{
d[node.v] = d[next] + node.w;
PQ.push(Node(node.v, d[node.v]));
}
}
}

return d[goal];
}