解題區/解題區 - UVa

UVa 721 - Invitation Cards

contents

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

Problem

ACM 參賽選手要到比賽會場，公車都是單向運行，求選手們來回的最少花費。

給一個有向圖，求從編號 1 到所有點的最短路徑總和，以及所有點到編號 1 的最短路徑總和。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

Sample Output

1
2
46
210

Solution

對一開始給定的圖，從編號 1 做一次 SSSP (單源最短路徑)，隨後再對題目給的反向圖做一次 SSSP 即可以得到所有點到編號 1 的最短路徑。

這一題很類似於 zerojudge 的地道問題。

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
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 1048576
vector< pair<int, long long> > g[MAXN], invg[MAXN];
long long dist[MAXN];
int inq[MAXN];
long long spfa(int source, int n, vector< pair<int, long long> > g[]) {
    for (int i = 0; i < n; i++) {
        dist[i] = 1LL<<60, inq[i] = 0;
    }
    queue<int> Q;
    int u, v;
    long long w;
    Q.push(source), dist[source] = 0;
    while (!Q.empty()) {
        u = Q.front(), Q.pop();
        inq[u] = 0;
        for (int i = 0; i < g[u].size(); i++) {
            v = g[u][i].first, w = g[u][i].second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inq[v]) {
                    Q.push(v), inq[v] = 1;
                }
            }
        }
    }
    long long ret = 0;
    for (int i = 0; i < n; i++) {
        ret += dist[i];
    }
    return ret;
}
int main() {
    int testcase, N, M;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d %d", &N, &M);
        for (int i = 0; i < N; i++) {
            g[i].clear(), invg[i].clear();
        }
        for (int i = 0; i < M; i++) {
            int x, y, c;
            scanf("%d %d %d", &x, &y, &c);
            x--, y--;
            g[x].push_back(make_pair(y, c));
            invg[y].push_back(make_pair(x, c));
        }
        long long ret = 0;
        ret += spfa(0, N, g);
        ret += spfa(0, N, invg);
        printf("%lld\n", ret);
    }
    return 0;
}
/*
 2
 2 2
 1 2 13
 2 1 33
 4 6
 1 2 10
 2 1 60
 1 3 20
 3 4 10
 2 4 5
 4 1 50
*/