PAT甲级：A1131 Subway Map (30分)

In the big cities, the subway systems always look so complex to the visitors. To give you some sense, the following figure shows the map of Beijing subway. Now you are supposed to help people with your computer skills! Given the starting position of your user, your task is to find the quickest way to his/her destination.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤ 100), the number of subway lines. Then N lines follow, with the i-th (i=1,⋯,N) line describes the i-th subway line in the format:

M S[1] S[2] … S[M]

where M (≤ 100) is the number of stops, and S[i]’s (i=1,⋯,M) are the indices of the stations (the indices are 4-digit numbers from 0000 to 9999) along the line. It is guaranteed that the stations are given in the correct order – that is, the train travels between S[i] and S[i+1] (i=1,⋯,M−1) without any stop.

Note: It is possible to have loops, but not self-loop (no train starts from S and stops at S without passing through another station). Each station interval belongs to a unique subway line. Although the lines may cross each other at some stations (so called “transfer stations”), no station can be the conjunction of more than 5 lines.

After the description of the subway, another positive integer K (≤ 10) is given. Then K lines follow, each gives a query from your user: the two indices as the starting station and the destination, respectively.

The following figure shows the sample map.

Note: It is guaranteed that all the stations are reachable, and all the queries consist of legal station numbers.

Output Specification:

For each query, first print in a line the minimum number of stops. Then you are supposed to show the optimal path in a friendly format as the following:

1
2
3
Take Line#X1 from S1 to S2.
Take Line#X2 from S2 to S3.
......

where Xi‘s are the line numbers and Si‘s are the station indices. Note: Besides the starting and ending stations, only the transfer stations shall be printed.

If the quickest path is not unique, output the one with the minimum number of transfers, which is guaranteed to be unique.

Sample Input:

1
2
3
4
5
6
7
8
9
4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
3
3011 3013
6666 2001
2004 3001

Sample Output:

1
2
3
4
5
6
7
8
9
10
2
Take Line#3 from 3011 to 3013.
10
Take Line#4 from 6666 to 1306.
Take Line#3 from 1306 to 2302.
Take Line#2 from 2302 to 2001.
6
Take Line#2 from 2004 to 1204.
Take Line#1 from 1204 to 1306.
Take Line#3 from 1306 to 3001.
  • 题意：给了一张地铁图，对任意给定的起点和终点，找到一条乘车方案，使行经站最少，如果有多个路线符合则输出换乘最少的（题目保证这是唯一的）。
  • 分析：这题实际上是个纸老虎，考察的是图的DFS，但是有不少需要注意的点（坑）。

主要有以下几步：

  1. 用什么方式表示这张图。因为题目中图的编号不是连续的，而且每个顶点的编号是四位数，所以这里要选用邻接表来存储图。
  2. 怎么找到路径并剪枝。如果只是用图的DFS遍历的话，那只能找到一条从起点到终点的路径，因为每个顶点只访问一次。首先这里铁路图肯定是连通图，之后，原来深度优先搜索的算法是走到哪个顶点就把那个点标记为已访问过，所以额外要改动的就是从某个顶点递归的DFS后再重新把这个点标记为可访问即可。同时，在DFS寻找所有路径的时候，为了适当缩短查找时间在DFS时添加cntStop参数记录当前结点的深度（实际上就是搭乘的站数），如果已经超过了之前记录的最小站数则提前退出，这一步是剪枝。
  3. 怎么计算换乘次数。要知道是否换乘就要知道乘车过程中线路是不是发生了改变，因为相邻的两个点肯定会在一条线路上，所以读入数据的时候需要保存相邻两点的线路编号，起初想法是用二维数组记录线路，但是如果是换乘点则至少会在两条线路上，所以使用哈希表通过 编号1 * 10000 + 编号2 作为键来标记这两点间的线路，同时从编号2到编号1亦需标记。之后计算换乘次数则先用preline变量记录初始的线路，随后从第二站开始遍历路径，如果发现线路改变则cnt加1，同时更新preline。
  4. 最后输出时，要求的只输出起点、换乘站和终点，因此思路和之前计算换乘次数是一致的，也是用preline先记录最开始的线路，同时这里还要用是preStop记录上一个输出的换乘站，最后还要输出最后一个换乘站到终点的记录就好了。

注意点：起初在dfs中判断是否更新最少乘车站时，如果乘车站数比之前记录的还要少，除了要更新最少乘车站数，也要把最少换乘数更新成当前这条线路的换乘数，因为乘车站数是第一尺标，换乘站是跟着它一起的呀，最开始没有更新，虽然只有两个测试点没过，但只有10分 ~_~！

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
#include <bits/stdc++.h>
using namespace std;
const int N = 10000;
int n, m, k, st, dest, minCntStop, minCntTransfer;
bool vis[N];
unordered_map<int, int> line;
vector<int> e[N], path, tempPath;
int getTransferCount(vector<int> &v) {
    int preline = line[v[0] * 10000 + v[1]], cnt = 0;
    for (int i = 1; i < v.size() - 1; i++) {
        int nowline = line[v[i] * 10000 + v[i + 1]];
        if (nowline != preline) {
            preline = nowline;
            cnt++;
        }
    }
    return cnt;
}
void dfs(int u, int cntStop) {
    if (cntStop > minCntStop) return;
    vis[u] = true;
    tempPath.push_back(u);
    if (u == dest) {
        int cntTransfer = getTransferCount(tempPath);
        if (cntStop < minCntStop || cntTransfer < minCntTransfer) {
            minCntTransfer = cntTransfer;
            minCntStop = cntStop;
            path = tempPath;
        }
        tempPath.pop_back();
        return;
    }
    for (auto next : e[u]) {
        if (!vis[next]) {
            dfs(next, cntStop + 1);
            vis[next] = false;
        }
    }
    tempPath.pop_back();
}
int main() {
    int preStop, stop;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &m, &preStop);
        for (int j = 0; j < m - 1; j++) {
            scanf("%d", &stop);
            e[preStop].push_back(stop);
            e[stop].push_back(preStop);
            line[preStop * 10000 + stop] = line[stop * 10000 + preStop] = i;
            preStop = stop;
        }
    }
    scanf("%d", &k);
    while (k--) {
        scanf("%d%d", &st, &dest);
        tempPath.clear();
        path.clear();
        minCntStop = minCntTransfer = 0x3f3f3f3f;
        fill(vis, vis + N, false);
        dfs(st, 0);
        printf("%d\n", path.size() - 1);
        int preline = line[path[0] * 10000 + path[1]], preStop = path[0];
        for (int i = 1; i < path.size() - 1; i++) {
            int nowline = line[path[i] * 10000 + path[i + 1]];
            if (nowline != preline) {
                printf("Take Line#%d from %04d to %04d.\n", preline, preStop, path[i]);
                preline = nowline;
                preStop = path[i];
            }
        }
        printf("Take Line#%d from %04d to %04d.\n", preline, preStop, dest);
    }
    return 0;
}