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;
}