a833. 3、沙漠旅行

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給一張帶正權有向圖,求路徑 1 -> n 的最短路徑。

Sample Input

1
2
3
4
5
6
4 5
1 3 1
2 4 2
1 2 2
3 4 2
2 4 1

Sample Output

1
3

Solution

標準的 sssp 問題 (單源最短路徑),一種是用 SPFA 鬆弛,另一種是比較穩定的 dijkstra algorithm,效率 $O(E \log V)$,寫法的模板如下,用 std::set<> 會比 std::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
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 500005;
const int MAXE = 500005;
const long long INF = 1LL<<60;
struct Edge {
int to, eid;
long long w;
Edge *next;
};
Edge edge[MAXE], *adj[MAXV];
int e = 0;
long long dist[MAXV];
void addEdge(int x, int y, long long v) {
edge[e].to = y, edge[e].w = v, edge[e].eid = e;
edge[e].next = adj[x], adj[x] = &edge[e++];
}
void dijkstra(int st, long long dist[], int n) {
typedef pair<long long, int> PLL;
for (int i = 0; i <= n; i++)
dist[i] = INF;
set<PLL> pQ;
PLL u;
pQ.insert(PLL(0, st)), dist[st] = 0;
while (!pQ.empty()) {
u = *pQ.begin(), pQ.erase(pQ.begin());
for (Edge *p = adj[u.second]; p; p = p->next) {
if (dist[p->to] > dist[u.second] + p->w) {
if (dist[p->to] != INF)
pQ.erase(pQ.find(PLL(dist[p->to], p->to)));
dist[p->to] = dist[u.second] + p->w;
pQ.insert(PLL(dist[p->to], p->to));
}
}
}
}
int main() {
int n, m;
int x, y, w;
while (scanf("%d %d", &n, &m) == 2) {
e = 0;
for (int i = 1; i <= n; i++)
adj[i] = NULL;
for (int i = 0; i < m; i++) {
scanf("%d %d %d", &x, &y, &w);
addEdge(x, y, w);
}
dijkstra(1, dist, n);
printf("%lld\n", dist[n]);
}
return 0;
}