L3-022 地铁一日游 (30 分)-PAT 团体程序设计天梯赛 GPLT

森森喜欢坐地铁。这个假期，他终于来到了传说中的地铁之城——魔都，打算好好过一把坐地铁的瘾！

魔都地铁的计价规则是：起步价 2 元，出发站与到达站的最短距离（即计费距离）每 K 公里增加 1 元车费。

例如取 K = 10，动安寺站离魔都绿桥站为 40 公里，则车费为 2 + 4 = 6 元。

为了获得最大的满足感，森森决定用以下的方式坐地铁：在某一站上车（不妨设为地铁站 A），则对于所有车费相同的到达站，森森只会在计费距离最远的站或线路末端站点出站，然后用森森美图 App 在站点外拍一张认证照，再按同样的方式前往下一个站点。

坐着坐着，森森突然好奇起来：在给定出发站的情况下（在出发时森森也会拍一张照），他的整个旅程中能够留下哪些站点的认证照？

地铁是铁路运输的一种形式，指在地下运行为主的城市轨道交通系统。一般来说，地铁由若干个站点组成，并有多条不同的线路双向行驶，可类比公交车，当两条或更多条线路经过同一个站点时，可进行换乘，更换自己所乘坐的线路。举例来说，魔都 1 号线和 2 号线都经过人民广场站，则乘坐 1 号线到达人民广场时就可以换乘到 2 号线前往 2 号线的各个站点。换乘不需出站（也拍不到认证照），因此森森乘坐地铁时换乘不受限制。

输入格式:
输入第一行是三个正整数 N、M 和 K，表示魔都地铁有 N 个车站 (1 ≤ N ≤ 200)，M 条线路 (1 ≤ M ≤ 1500)，最短距离每超过 K 公里 (1 ≤ K ≤ 106)，加 1 元车费。

接下来 M 行，每行由以下格式组成：

<站点1><空格><距离><空格><站点2><空格><距离><空格><站点3> … <站点X-1><空格><距离><空格><站点X>

其中站点是一个 1 到 N 的编号；两个站点编号之间的距离指两个站在该线路上的距离。两站之间距离是一个不大于 106 的正整数。一条线路上的站点互不相同。

注意：两个站之间可能有多条直接连接的线路，且距离不一定相等。

再接下来有一个正整数 Q (1 ≤ Q ≤ 200)，表示森森尝试从 Q 个站点出发。

最后有 Q 行，每行一个正整数 Xi**，表示森森尝试从编号为 **Xi 的站点出发。

输出格式:
对于森森每个尝试的站点，输出一行若干个整数，表示能够到达的站点编号。站点编号从小到大排序。

输入样例:
6 2 6
1 6 2 4 3 1 4
5 6 2 6 6
4
2
3
4
5

输出样例:
1 2 4 5 6
1 2 3 4 5 6
1 2 4 5 6
1 2 4 5 6

分析：Ter[i]数组表示第i个节点是不是两端的站点，Station中存储站点i直接能留下认证照的站点，Ans中存储站点i最终能留下认证照的站点，Fur_Dis中存储每个花费下能到达的最远距离，由于所有票价都有一个2的基础，所以加布加都可以。刚开始将地图的信息输入至Edge中，并记录两侧端点的信息。由于相同的两个站点也可能有不同距离的路线，所以这里需要取最小值。然后用Floyd最短路算法求出两个站点之间最短的路线。然后再遍历出每个节点到达的所有距离需要多少花费，如果该花费是最小值，说明该站点可以拍照。最后再通过简单的dfs，找出一个站点能以其他可换乘的车站作为中转点，可以到达的所有站点～

#include <bits/stdc++.h>
using namespace std;
const int Mx = 1e9;
int N, M, K, Q, from, to, dis, Ter[201], Edge[201][201];
map<int, set<int>> Station;
map<int, set<int>> Ans;
void DFS(int Start, int Now) {
    for (auto it : Station[Now]) {
        if (Ans[Start].count(it)) continue;
        Ans[Start].insert(it);
        DFS(Start, it);
    }
}
int main() {
    for (int i = 1; i <= 200; i++)
        for (int j = 1; j <= 200; j++)
            Edge[i][j] = Mx;
    scanf("%d %d %d", &N, &M, &K);
    while (M--) {
        scanf("%d", &from);
        Ter[from] = 1;
        while (1) {
            scanf("%d %d", &dis, &to);
            Edge[from][to] = Edge[to][from] = min(Edge[from][to], dis);
            from = to;
            if (getchar() == '\n') break;
        }
        Ter[to] = 1;
    }
    for (int k = 1; k <= N; k++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++) 
                if (i != j) Edge[i][j] = min(Edge[i][j], Edge[i][k] + Edge[k][j]);
    for (int i = 1; i <= N; i++) {
        map<int, int> Fur_Dis;
        Ans[i].insert(i);
        for (int j = 1; j <= N; j++) {
            if (Edge[i][j] != Mx) {
                if (Ter[j] == 1) Station[i].insert(j);
                if (Edge[i][j] > Fur_Dis[Edge[i][j] / K]) Fur_Dis[Edge[i][j] / K] = Edge[i][j];
            }
        }
        for (int j = 1; j <= N; j++)
            if (Edge[i][j] == Fur_Dis[Edge[i][j] / K]) Station[i].insert(j);
    }
    for (int i = 1; i <= N; i++) DFS(i, i);
    scanf("%d", &Q);
    while (Q--) {
        scanf("%d", &from);
        for (auto it : Ans[from]) 
            printf("%d%c", it, (it != *Ans[from].rbegin()) ? ' ' : '\n');
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int Mx = 1e9;

int N, M, K, Q, from, to, dis, Ter[201], Edge[201][201];

map<int, set<int>> Station;

map<int, set<int>> Ans;

void DFS(int Start, int Now) {

for (auto it : Station[Now]) {

if (Ans[Start].count(it)) continue;

Ans[Start].insert(it);

DFS(Start, it);

}

int main() {

for (int i = 1; i <= 200; i++)

for (int j = 1; j <= 200; j++)

Edge[i][j] = Mx;

scanf("%d %d %d", &N, &M, &K);

while (M--) {

scanf("%d", &from);

Ter[from] = 1;

while (1) {

scanf("%d %d", &dis, &to);

Edge[from][to] = Edge[to][from] = min(Edge[from][to], dis);

from = to;

if (getchar() == '\n') break;

}

Ter[to] = 1;

}

for (int k = 1; k <= N; k++)

for (int i = 1; i <= N; i++)

for (int j = 1; j <= N; j++)

if (i != j) Edge[i][j] = min(Edge[i][j], Edge[i][k] + Edge[k][j]);

for (int i = 1; i <= N; i++) {

map<int, int> Fur_Dis;

Ans[i].insert(i);

for (int j = 1; j <= N; j++) {

if (Edge[i][j] != Mx) {

if (Ter[j] == 1) Station[i].insert(j);

if (Edge[i][j] > Fur_Dis[Edge[i][j] / K]) Fur_Dis[Edge[i][j] / K] = Edge[i][j];

}

for (int j = 1; j <= N; j++)

if (Edge[i][j] == Fur_Dis[Edge[i][j] / K]) Station[i].insert(j);

}

for (int i = 1; i <= N; i++) DFS(i, i);

scanf("%d", &Q);

while (Q--) {

scanf("%d", &from);

for (auto it : Ans[from])

printf("%d%c", it, (it != *Ans[from].rbegin()) ? ' ' : '\n');

}

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版