PAT甲级1131Subway Map

Posted on | | Visitors:
Words count in article: 629 字 | Reading time ≈ 3 分

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805347523346432

题解

题目要求

  • 给定起点和目标地，找到最快的路

  • 输入

    • N：正整数，不超过100，地铁线路的数量，索引为[1,n]
    • N条地铁线路：M个站点，站点索引为[0000,9999]
      • 两条地铁线路不会经过同一条边（站到站）
      • 可能存在环，但没有自环
      • 每个站点最多有5条线路经过
    • K：正整数，不超过10，查询的数量
    • K对起点和终点

  • 输出

    对于每个查询，输出最少经过的站数。如果有多个解，输出换线最少的解。

解题思路

  • 因为存在环，所以在DFS时需要用visit数组表示某个车站是否已经DFS过。其实只要存在可以从多个结点到达某个结点V的情况，就应该设置visit数组标记是否已访问过结点V，如果访问过则不用再访问。
  • 注意输出要按四位输出

代码

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
// Problem: PAT Advanced 1131
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805347523346432
// Tags: 图 DFS

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 10000;
int line[MAXN][MAXN];
bool visited[MAXN];
vector<int> nextStop[MAXN];
vector<int> tempPath, ansPath;
int tempTransfer, ansTransfer;
int n, m, k, start, destination;

void dfs(int stop,int preLine){
    if (visited[stop])
        return ;
    tempPath.push_back(stop);
    visited[stop] = true;
    if (stop == destination){
        if (tempPath.size() < ansPath.size()){
            ansPath = tempPath;
            ansTransfer = tempTransfer;
        }else if(tempPath.size() == ansPath.size() && tempTransfer < ansTransfer){
            ansPath = tempPath;
            ansTransfer = tempTransfer;
        }
    }
    else{
        for (auto it = nextStop[stop].begin(); it != nextStop[stop].end(); it++){
            bool transferFlag = (line[stop][*it] != preLine);
            if (transferFlag)
                tempTransfer++;
            dfs(*it, line[stop][*it]);
            if (transferFlag)
                tempTransfer--;
        }
    }
    tempPath.pop_back();
    visited[stop] = false;
}

int main()
{
    scanf("%d", &n);
    int u, v;
    for (int i = 1; i <= n; i++){
        scanf("%d%d", &m, &u);
        for (int j = 0; j < m - 1; j++){
            scanf("%d", &v);
            line[u][v] = i;
            line[v][u] = i;
            nextStop[u].push_back(v);
            nextStop[v].push_back(u);
            u = v;
        }
    }
    scanf("%d", &k);
    while (k--){
        scanf("%d%d", &start, &destination);
        tempTransfer = -1;
        ansTransfer = MAXN;
        tempPath.clear();
        ansPath.resize(MAXN);
        dfs(start, 0);
        printf("%d\n", ansPath.size() - 1);
        int tempStart = start, preLine = line[ansPath[0]][ansPath[1]];
        for(int i = 0; i < ansPath.size() - 1; i++){
            if (preLine != line[ansPath[i]][ansPath[i + 1]]){ // 要换线
                printf("Take Line#%d from %04d to %04d.\n", preLine, tempStart, ansPath[i]);
                tempStart = ansPath[i];
                preLine = line[ansPath[i]][ansPath[i + 1]];
            }
        }
        printf("Take Line#%d from %04d to %04d.\n", preLine, tempStart, ansPath.back());
    }
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!