題目: 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 演算法學習筆記