PAT甲级 1131 Subway Map (30分) 无向图的dfs + unordered_map的巧妙应用

雨点打透心脏的1/2处 2023-07-23 03:42 7阅读 0赞

题目链接：[https://pintia.cn/problem-sets/994805342720868352/problems/994805347523346432][https_pintia.cn_problem-sets_994805342720868352_problems_994805347523346432]

# 题意 #

给出地铁路线，依据：最少乘坐的站点>最少换乘次数

# 分析 #

本题是比较复杂的无向图DFS题目，必须用DFS，没有别的好办法了（因为有人说[用Dijkstra+DFS会超时][Dijkstra_DFS]）。

1.整个地铁线路，视为无向图，用二维数组表示；  
2.站点和几号线的换算问题，用unordered\_map**保存每两个相邻站中间的线路是几号线**

# 满分代码 #

源自[liuchuo][]，注释是我加的。

#include <iostream>
    #include <vector>
    #include <unordered_map>
    using namespace std;
    vector<vector<int>> v(10000);//地铁线路图 v[a]是一维向量，存a的所有相邻节点
    int visit[10000];//DFS中标记节点有无被访问过
    int minCnt;//最小站点数目
    int minTransfer;//最小换乘次数
    int start;//每次查询的起点站
    int end1;//每次查询的终点站
    unordered_map<int, int> line;//key为两个站的4+4位编号，value为几号线
    vector<int> path;//路线最优解
    vector<int> tempPath;//临时存放的线路解
    int transferCnt(vector<int> a) {//计算这条路线换乘的次数
        int cnt = -1, preLine = 0;
        for (int i = 1; i < a.size(); i++) {
            if (line[a[i-1]*10000+a[i]] != preLine) cnt++;
            preLine = line[a[i-1]*10000+a[i]];
        }
        return cnt;
    }
    void dfs(int node, int cnt) {
        if (node == end1 && (cnt < minCnt || (cnt == minCnt && transferCnt(tempPath) < minTransfer))) {
            minCnt = cnt;
            minTransfer = transferCnt(tempPath);
            path = tempPath;
        }
        if (node == end1) return;
        for (int i = 0; i < v[node].size(); i++) {
            if (visit[v[node][i]] == 0) {
                visit[v[node][i]] = 1;
                tempPath.push_back(v[node][i]);
                dfs(v[node][i], cnt + 1);
                visit[v[node][i]] = 0;
                tempPath.pop_back();
            }
        }
    }
    int main() {
        int n, m, k, pre, temp;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &m, &pre);
            for (int j = 1; j < m; j++) {
                scanf("%d", &temp);
                v[pre].push_back(temp);
                v[temp].push_back(pre);
                line[pre*10000+temp] = line[temp*10000+pre] = i + 1;
                pre = temp;
            }
        }
        scanf("%d", &k);
        for (int i = 0; i < k; i++) {
            scanf("%d%d", &start, &end1);
            minCnt = 99999, minTransfer = 99999;
            tempPath.clear();
            tempPath.push_back(start);
            visit[start] = 1;
            dfs(start, 0);
            visit[start] = 0;
            printf("%d\n", minCnt);
            int preLine = 0, preTransfer = start;
            for (int j = 1; j < path.size(); j++) {
                if (line[path[j-1]*10000+path[j]] != preLine) {
                    if (preLine != 0) printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer, path[j-1]);
                    preLine = line[path[j-1]*10000+path[j]];
                    preTransfer = path[j-1];
                }
            }
            printf("Take Line#%d from %04d to %04d.\n", preLine, preTransfer, end1);
        }
        return 0;
    }

[https_pintia.cn_problem-sets_994805342720868352_problems_994805347523346432]: https://pintia.cn/problem-sets/994805342720868352/problems/994805347523346432
[Dijkstra_DFS]: https://www.cnblogs.com/weedboy/p/7356437.html
[liuchuo]: https://blog.csdn.net/liuchuo/article/details/68925193?locationNum=4&fps=1