題目： UVa - 10986 - Sending email
題目說明
有 n 台 SMTP 伺服器透過 m 條網絡線連接，每條網絡線連接兩台伺服器，透過每條網絡線發送電子郵件有一定的延遲時間（以毫秒為單位）。 假設伺服器本身不會造成延遲，請問沿著網絡線從伺服器 s 向伺服器 t 發送電子郵件所需的最短時間是多少？
引用自：【題解】UVa 10986 Sending email - Yui Huang 演算法學習筆記
Input： 第一行為一整數，表示有幾組測資，每組測資第一行為四個整數，分別為 n、m、s、t，後面 m 行每行有三個整數 u、v、w，表示伺服器 u、v 可互相傳送電子郵件，且所需時間為 w。
Output： 輸出沿著網絡線從伺服器 s 向伺服器 t 發送電子郵件所需的最短時間。若無法傳送到則輸出 "unreachable"。
解題思路
這個解法需要有 Dijkstra 演算法的概念。
使用 Dijkstra 搭配 Priority_queue 求解即可。記得建雙向邊。
參考解法
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
77
78
79
80
81
82
83
| #include <iostream>
#include <climits>
#include <queue>
#include <unordered_map>
using namespace std;
static auto __ = []
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
return 0;
}();
struct point
{
int u;
int w;
bool operator>(const point& r) const { return w > r.w; }
};
unordered_map<int, vector<pair<int, int>>> edges;
int value[20000];
bool visited[20000];
priority_queue<point, vector<point>, greater<point>> pq;
void init(int n)
{
edges.clear();
for (int i = 0; i < n; ++i) value[i] = INT_MAX, visited[i] = false;
}
void dijkstra(int start)
{
pq.push({ start, value[start] = 0 });
while (!pq.empty())
{
auto [u, val] = pq.top();
visited[u] = true;
pq.pop();
for (auto& [v, w] : edges[u])
{
if (visited[v]) continue;
int tmp = val + w;
if (value[v] > tmp) pq.push({ v, value[v] = tmp });
}
}
}
int main()
{
int T, Case = 0;
cin >> T;
while (T--)
{
int n, m, s, t;
cin >> n >> m >> s >> t;
init(n);
while (m--)
{
int u, v, w;
cin >> u >> v >> w;
edges[u].push_back({ v, w });
edges[v].push_back({ u, w });
}
dijkstra(s);
cout << "Case #" << ++Case << ": ";
if (value[t] != INT_MAX) cout << value[t] << '\n';
else cout << "unreachable\n";
}
}
|
參考資料
【題解】UVa 10986 Sending email - Yui Huang 演算法學習筆記
