AcWing3403. 我想回家

某国正处于激烈的内战之中，该国的各个城市按照支持领导人的不同分属两个阵营。

作为一个商人，M 先生并不关心政治，但他能够感受到目前事态的严峻。

你需要帮助他尽快回家。

出于安全的考虑，你所提供的回家线路中，最多只能包含一条连接两个不同阵营城市的道路。

请你计算，M 先生回家所需花费的最短时间。

输入格式

输入包含多组测试数据。

每组数据第一行包含整数 N，表示该国家的城市数量。

第二行包含整数 M，表示该国家的道路数量。

接下来 M 行，每行包含三个整数 A,B,T，表示城市 A 和城市 B 之间存在一条道路，通过它的时间为 T。

最后一行包含 N 个整数 1 或 2，其中的第 i 个整数是 1，则表示城市 i 位于阵营 1，否则，表示城市 i 位于阵营 2。

所有城市编号 1 ~ N。

为了简化问题，我们假设 M 先生是从城市 1 出发，目的地是城市 2，并且城市 1 一定位于阵营 1，城市 2 一定位于阵营 2。

注意，所有道路都是双向的，且两个城市之间最多只有一条道路。

输入 N=0 时，表示输入结束。

输出格式

每组数据输出一行一个结果，表示最短时间。如果无法到达目的地，则输出 -1。

数据范围

每个输入最多包含 10 组数据。
2 < N < 600,
0 < M < 10000,
1 < A,B < N,
1 < T < 500

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
1
1 2 100
1 2
3
3
1 2 100
1 3 40
2 3 50
1 2 1
5
5
3 1 200
5 3 150
2 5 160
4 3 170
4 2 170
1 2 2 2 1
0

输出样例：

1
2
3
100
90
540

算法思想

分析输入：

  1. 第一行：点数n
  2. 第二行：边数m
  3. 第三行：边add(a,b,c)
  4. 最后一行：每个点的阵营team[N]

核心思想：
A国最短路径 + 连接两国的唯一一条路 + B国最短路径 = 答案

QQ_1721898317357

难点：

  1. 查表
    0、1、2、3、4、5、6、7、8、9、……
    看成：[0, 1]、[1, 2]、[3, 4]、[5, 6]、[7, 8]、[9, 10]、……
    1
    int a = e[i ^ 1], b = e[i];
    1
    2
    3
    4
    对于： 0 -> 1
    a = 0, b= 1; 
    `0 ^ 1 = 1`
    `1 ^ 1 = 0`
    1
    2
    3
    4
    对于： 2 -> 3
    a = 2, b= 3; 
    `2 ^ 1 = 3`
    `3 ^ 1 = 2`

idx一定是这样增长的，所以任取终边一定能找到其反向边

代码实现

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
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

// 题目给的边范围[0, 10000]
// 由于是无向边，每条边建两次，所以M至少要超过20000
const int N = 610, M = 20010, INF = 0X3F3F3F3F;

int h[N], e[M], ne[M], w[M], idx;
int distA[N], distB[N], team[N];
int n, m;
bool st[N];

void add(int a, int b, int c){
    e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}

// 复用型 dijkstra
// 起点、起点所属阵营、起点阵营的dist表
void dijkstra(int start, int camp, int dist[]){
    // 因为是复用，所以还要 重置dist和st
    // 细节是 sizeof distA，但是memset执行对象是 dist
    memset(dist, 0x3f, sizeof distA);
    memset(st, false, sizeof st);
    // 起点距离为0
    dist[start] = 0;
    
    for(int i = 1; i <= n; i++){
        int t = -1;
        
        for(int j = 1; j <= n; j++){
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }
        
        st[t] = true;
        
        // 更新邻接表
        for(int j = h[t]; ~j; j = ne[j]){
            // 邻接点
            int k = e[j];
            // 如果不是同一个阵营，则什么也不做
            if(team[k] != camp) continue;
            // 是同一个阵营就更新
            dist[k] = min(dist[k], dist[t] + w[j]);
        }
    }
}

int main(){
    
    while(cin >> n, n){
        // 复用就需要重置图
        memset(h, -1, sizeof h);
        idx = 0;
        
        cin >> m;
        while(m --){
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);
            add(b, a, c);
        }
        // 阵营输入
        for(int i = 1; i <= n; i++) cin >> team[i];
        
        // A国最短路径 + 连接两国的唯一一条路 + B国最短路径 = 答案
        dijkstra(1, 1, distA);
        dijkstra(2, 2, distB);
        
        // 查表
        int res = INF; // 没有答案的话，res还是 INF
        for(int i = 0; i < idx; i++){
            // [0,1]、[2,3]、...:规律
            // 0^1 = 1
            // 1^1 = 0
            // 建图的时候，add(a,b,c),add(b,a,c)
            // 正向边和反向边，一对一对建的
            // 此时 a 是反向边，b 是正向边
            int a = e[i ^ 1], b = e[i];
            if(team[a] == 1 && team[b] == 2){
                res = min(res, distA[a] + w[i] + distB[b]);
            }
        }
        
        // 无解输出-1，否则输出值
        if(res == INF) puts("-1");
        else cout << res << endl;
    }
    
    return 0;
}