Skip to content

Latest commit

 

History

History
111 lines (101 loc) · 4.06 KB

1131. Subway Map.md

File metadata and controls

111 lines (101 loc) · 4.06 KB

pat甲级1131 Subway Map

输入输出格式

输入第一行包含一个正整数N，表示地铁线路的数量。接下来N行，第i行（$i=1,2,\cdots,N$）线以M S[1] S[2] ... S[M]的格式描述第i条地铁线，其中M是停靠点的数量，S[i]的是沿线的站点的索引（索引是从0000到9999的4位数字）。尽管这些地铁线在某些站点（称为换乘站点）可能会彼此交叉，但连续的两个地铁站只属于唯一的地铁线。接下来一行给出一个正整数K。接下来K行，每行都会提出一个查询：给出起始地和目的地，找到最短路径。

对于每个查询，首先在一行中打印最少的停靠点数。然后，应该以下面的格式显示最佳路径：

Take Line#X1 from S1 to S2.
Take Line#X2 from S2 to S3.
......

其中Xi是线号，Si是车站索引。注意：除起点和终点站外，仅应打印换乘站。如果最短路径不是唯一的，请输出换乘次数最少的路径，确保该路径唯一。

数据规模

$$N,M<=100$$

算法设计

本题有一定难度。显然这是一个无向无权图，结点编号在0~9999之间，如果直接定义一个二维数组，肯定会内存超限。可以定义一个unordered_map<int,int>lines来存储两个结点之间的边属于那条线路，假设边两端的结点编号为a和b，那么lines的键可以用a*10005+b来表示，值表示这条边所属线路。

用邻接表存储整个图。由于这是一个无权图，最短路可以用BFS算法来解决。需要额外注意的是当最短路不唯一时，要选择换乘站少的路径，这一点直接在BFS算法中计算最短路径长度时同时进行更新是不行的，可以保存下来所有的最短路径，通过DFS遍历所有最短路径找出其中换乘站最少的路径。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 1e4 + 5;
vector<vector<gg>> graph(MAX), past(MAX);
unordered_map<gg, gg> lines;
vector<gg> dis(MAX), path;
vector<array<gg, 2>> ans;
void bfs(gg v) {
    fill(dis.begin(), dis.end(), INT_MAX);
    fill(past.begin(), past.end(), vector<gg>());
    queue<gg> q;
    q.push(v);
    dis[v] = 0;
    for (gg d = 0; not q.empty(); ++d) {
        gg s = q.size();
        for (gg i = 0; i < s; ++i) {
            v = q.front();
            q.pop();
            dis[v] = d;
            for (gg i : graph[v]) {
                if (dis[i] > dis[v] + 1) {
                    q.push(i);
                    dis[i] = dis[v] + 1;
                    past[i] = {v};
                } else if (dis[i] == dis[v] + 1) {
                    past[i].push_back(v);
                }
            }
        }
    }
}
void dfs(gg v, gg s) {
    path.push_back(v);
    if (v == s) {
        vector<array<gg, 2>> trans{{s, -1}};
        for (gg i = path.size() - 2; i > 0; --i) {
            if (lines[path[i - 1] * MAX + path[i]] !=
                lines[path[i] * MAX + path[i + 1]]) {
                trans.push_back({path[i], lines[path[i] * MAX + path[i + 1]]});
            }
        }
        trans.push_back({path[0], lines[path[1] * MAX + path[0]]});
        if (ans.empty() or trans.size() < ans.size()) {
            ans = trans;
        }
    }
    for (gg i : past[v]) {
        dfs(i, s);
    }
    path.pop_back();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    gg ni, mi, ki, ai, bi, s, e;
    cin >> ni;
    for (gg i = 1; i <= ni; ++i) {
        cin >> mi >> ai;
        while (--mi) {
            cin >> bi;
            lines[ai * MAX + bi] = i;
            lines[bi * MAX + ai] = i;
            graph[ai].push_back(bi);
            graph[bi].push_back(ai);
            ai = bi;
        }
    }
    cin >> ki;
    cout << setfill('0');
    while (ki--) {
        cin >> s >> e;
        bfs(s);
        ans.clear();
        dfs(e, s);
        cout << dis[e] << "\n";
        for (gg i = 1; i < ans.size(); ++i) {
            cout << "Take Line#" << ans[i][1] << " from " << setw(4)
                 << ans[i - 1][0] << " to " << setw(4) << ans[i][0] << ".\n";
        }
    }
    return 0;
}