个人练习-PAT甲级-1131 Subway Map

题目链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805347523346432

题目大意：给出一个图，节点是许多地铁站，地铁站由许多边连接起来。一个地铁站可能属于好几条线路，在多条线路上的地铁站是【换乘点】。

现在给出地铁站的拓扑结构，给出K个query，每个query给出一个起点和一个终点。求从起点到终点的最短路径（认为所有边长度都为1），如果有多条，求【换乘次数】最少的那条。
输出格式中，先输出路径长度（经过站点数）。再按顺序输出：起点、经过的换乘点、终点。即中间不是换乘的那些站点不用输出。

思路：
一开始无脑上Dijkstra，尽管处理了路径长度相同时计算换乘次数的bug，但还是有几个点没过，最后一个点还超时。

看了网上一些解法后，恍然发觉DFS非常合适做这个。因为Dijkstra在求最短路径的时候实际上是把【从起点到全图每一个点的最短路径】求出来了，工作量很大，我们实际上只需要【从起点到终点的最短路径】即可。

于是换用DFS，按自己的思路写了一遍，结果最后一个点还是超时。对比了下柳神的代码，发现是DFS时【寻找每个节点的相邻节点】这一步骤不同。柳神是用了一个二维vector来存，我原来的写法是【读入数据时，记录下来所有出现过的节点编号，存在all_sta这个数组里】，需要找相邻节点时就从里面遍历，这样子每次遍历次数会小于N，比全部遍历略快，但实际上复杂度/数量级还是相同的…于是乖乖开了个大的二维vector来存，通过最后一个测试点。

感想：这种多条件的最短路径问题之前也好像遇到过，想想不难，DFS、BFS、Dijkstra都可以上，实际上写起来还是有很多细节要注意的。

完整代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 


using namespace std;


int N, s1, s2, min_cnt, min_trans;
const int MAX = 1000;
int G[10000][10000];
bool known[10000];
vector<int> adj[10000];
vector<int> path, tmp_path;


void initialize(int s1) {
    tmp_path.clear();
    min_cnt = MAX;
    min_trans = MAX;
    for (int i = 0; i < 10000; i++)
        known[i] = false;

    tmp_path.push_back(s1);
    known[s1] = true;
}


int calTrans(vector<int> path) {
    int trans = -1, last_line = 0;
    for (int i = 1; i < path.size(); i++) {
        int now_line = G[path[i]][path[i-1]];
        if (now_line != last_line) {
            last_line = now_line;
            trans++;
        }
    }
    return trans;
}


void DFS(int node, int cnt) {
    if (node == s2) {
        if (cnt < min_cnt) {
            min_cnt = cnt;
            min_trans = calTrans(tmp_path);
            path = tmp_path;
        }
        else if (cnt == min_cnt) {
            if (calTrans(tmp_path) < min_trans) {
                min_trans = calTrans(tmp_path);
                path = tmp_path;
            }
        }
        else;

        return;
    }

    for (int i = 0; i < adj[node].size(); i++) {
        int v = adj[node][i];
        if (!known[v] && G[node][v]) {
            known[v] = true;
            tmp_path.push_back(v);
            DFS(v, cnt+1);
            known[v] = false;
            tmp_path.pop_back();
        }
    }


}


void output(int s1, int s2, vector<int> path) {
    printf("%d\n", min_cnt);
    int last_line = 0, last_trans = s1;
    for (int i = 1; i < path.size(); i++) {
        int now_line = G[path[i-1]][path[i]];
        if (now_line != last_line) {
            if (last_line != 0)
                printf("Take Line#%d from %04d to %04d.\n", last_line, last_trans, path[i-1]);
            last_line = now_line;
            last_trans = path[i-1];
        }
    }
    printf("Take Line#%d from %04d to %04d.\n", last_line, last_trans, s2);
}


int main() {
    scanf("%d", &N);

    for (int i = 1; i <= N; i++) {
        int M, pre;
        scanf("%d", &M);
        for (int j = 0; j < M; j++) {
            int sta;
            scanf("%d", &sta);
            if (j != 0) {
                G[pre][sta] = G[sta][pre] = i;
                adj[pre].push_back(sta);
                adj[sta].push_back(pre);
            }
            else
                pre = sta;
            pre = sta;
        }
    }

    int K;
    scanf("%d", &K);
    for (int i = 0; i < K; i++) {
        scanf("%d %d", &s1, &s2);
        initialize(s1);
        DFS(s1, 0);
        output(s1, s2, path);
    }


    return 0;
}

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130