如果用常规的图的存储，最短路径相同时，换乘次数最少不好求。因此可以采用添加边的方式，每个地铁线路的各个点直接都添加一条边（即若该地铁线路有n个站点，则添加$C_{n}^{2}$条边），边的权值为两点之间的距离（即经过站点数量）。这样最短路径相同时，换乘次数最少就==转化为==求最短路径相同时，求边数最少，即双关键字的dijkstra

注意最大点数和最大边数，尤其注意此种做法的最大边数：

本题数据最多有100条线路，每条线路最多有100个站点，所以最多站点的情况为100条线路上每条线路都有100个站点，即最多站点为100 * 100 = 10000=1e4

由于点数已经到了1e4了，所以即使是开bool类型的领接矩阵来存，也要$1e4\times1e4=10^8B$，因为$1MB=2^{20}B=(2^{10})^2B≈(10^3)^2B=10^6B$，即$1B≈10^{-6}MB$，所以$10^8B≈10^{-6}\times10^8=10^2=100MB > 64MB$，那么直接会MLE，所以应该用领接表存

每条线最多100个站，就是$C_{100}^{2} = \frac{100(100+1)}2$条边，最多100条线，总共就是$\frac{100(100+1)}2 \times100\approx 10^6$条边

在建边时特别需要注意的点为，有可能线路为环形线路，建边的权值（即经过站点数量）取环形线上经过站点数量最小的一侧

此外，本题的代表点的标识为字符串，因此需要建立映射

unordered_map<string, int> mp_to_number;// 站点编号的字符串 -> 数字，从0开始
unordered_map<int, string> mp_to_string;// 站点编号的数字 -> 字符串

建边代码如下：

for (int j = 0; j < m; j++) {
    cin >> stops[j];
    if (mp_to_number.count(stops[j]) == 0) {
        mp_to_number[stops[j]] = map_id;// 存映射
        mp_to_string[map_id++] = stops[j];
    }
}
for (int j = 0; j < m; j++) {// 二重循环 在这条线路上的任意两点间 建边
    for (int k = 0; k < j; k++) {
        int len;
        // 是否是环形线
        if (stops[0] == stops[m - 1]) {
            len = min(j - k, m - 1 - (j - k));//环形线取经过站点数量最小的一侧，因为环形线最后一个点和起点是同一个点 所以要m - 1
        } else {
            len = j - k;
        }
        int a = mp_to_number[stops[j]];

        int b = mp_to_number[stops[k]];

        add(a, b, len, i);
        add(b, a, len, i);
    }
}

这题的点数达到了1e4，因此用朴素版的dijkstra算法肯定会超时，要用堆优化版本的dijkstra

#include <iostream>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <vector>

using namespace std;

const int N = 1e4 + 10, M = 1e6 + 10;

struct Node {
    int distance, ver;
};

bool operator<(Node lhs, Node rhs) {
    return lhs.distance > rhs.distance;
}

int n;

int h[N], e[M], ne[M], w[M], id[M], idx;// e数组存储的是站(点)的编号。这里的id数组存储的是线路编号
string stops[110];
unordered_map<string, int> mp_to_number;// 站点编号的字符串 -> 数字，从0开始
unordered_map<int, string> mp_to_string;// 站点编号的数字 -> 字符串

int map_id = 1;// 站点编号的字符串映射成数字的id，从1开始

/*
dist[j]存储的是（目前，目前指的是迭代过程中）起点到j最短的距离
cnt[j]表示（目前，目前指的是迭代过程中）从起点走到j的最小边数，即换乘的次数
pre[j]为（目前，目前指的是迭代过程中）从起点到j的最短路径(若最短路径长度相同，则取最小边数)中j的前驱节点
info[j]表示（目前，目前指的是迭代过程中）从起点到j的最短路径(若最短路径长度相同，则取最小边数)中，到j站(点)的换乘信息，即换乘几号线从哪个站(点)到j站(点)的
*/
int dist[N];
int cnt[N];
int pre[N];
string info[N];
bool st[N];

void add(int a, int b, int weight, int line_id) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx, w[idx] = weight, id[idx] = line_id, idx++;
}

void dijkstra(int start, int end) {
    // 多组数据的dijkstra一定要重置数据
    memset(dist, 0x3f, sizeof(dist));
    memset(cnt, 0, sizeof(cnt));
    memset(st, 0, sizeof(st));
    dist[start] = 0;
    priority_queue<Node> heap;
    heap.push({0, start});
    while (!heap.empty()) {
        auto t = heap.top();
        heap.pop();
        int distance = t.distance, ver = t.ver;

        /*
        这里为什么可以break,因为当你取出终点时，说明所有到达终点的方式已经全部更新了
        已找到最优解可以退出了
        */
        if (ver == end) {
            break;
        }
        if (st[ver]) {
            continue;
        }
        st[ver] = true;

        // 使用领接表存储图时，这里很容易写错
        // for循环遍历与点相连的所有边时，这里的i是指地址，即idx
        // j是指该i这个地址处的节点编号
        // 一定要注意两点相连边的权值为w[i]，而不是w[j]
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > distance + w[i]) {
                dist[j] = distance + w[i];
                cnt[j] = cnt[ver] + 1;
                pre[j] = ver;
                heap.push({dist[j], j});
                info[j] =
                        "Take Line#" + to_string(id[i]) + " from " + mp_to_string[ver] + " to " + mp_to_string[j] + ".";
            } else if (dist[j] == distance + w[i] && cnt[ver] + 1 < cnt[j]) {
                cnt[j] = cnt[ver] + 1;
                pre[j] = ver;
                info[j] =
                        "Take Line#" + to_string(id[i]) + " from " + mp_to_string[ver] + " to " + mp_to_string[j] + ".";
            }
        }
    }
    cout << dist[end] << endl;
    vector<string> path;
    for (int i = end; i != start; i = pre[i]) {
        path.push_back(info[i]);
    }
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << path[i] << endl;
    }
}

int main() {
    memset(h, -1, sizeof(h));
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int m;
        cin >> m;
        for (int j = 0; j < m; j++) {
            cin >> stops[j];
            if (mp_to_number.count(stops[j]) == 0) {
                mp_to_number[stops[j]] = map_id;// 存映射
                mp_to_string[map_id++] = stops[j];
            }
        }
        for (int j = 0; j < m; j++) {// 二重循环 在这条线路上的任意两点间 建边
            for (int k = 0; k < j; k++) {
                int len;
                // 是否是环形线
                if (stops[0] == stops[m - 1]) {
                    len = min(j - k, m - 1 - (j - k));//环形线取经过站点数量最小的一侧，因为环形线最后一个点和起点是同一个点 所以要m - 1
                } else {
                    len = j - k;
                }
                int a = mp_to_number[stops[j]];

                int b = mp_to_number[stops[k]];

                add(a, b, len, i);
                add(b, a, len, i);
            }
        }
    }
    int k;
    cin >> k;
    while (k--) {
        string a, b;
        cin >> a >> b;
        int start = mp_to_number[a], end = mp_to_number[b];
        dijkstra(start, end);
    }
    return 0;
}

py代码：

使用defaultdict，因此可以使用领接矩阵来存图（即字典的字典），假设g为领接矩阵

并且要注意：g[i][j]是一个列表，列表里每个元素的类型为Edge，为什么g[i][j]要设为一个列表？因为点i⇨点j可能有重边，并且重边在这个题目的含义为不同的线路，因此g[i][j]必须为列表

import heapq
from collections import defaultdict

# g[i][j]是一个列表，列表里每个元素的类型为Edge，为什么g[i][j]要设为一个列表？因为点i⇨点j可能有重边，并且重边在这个题目的含义为不同的线路，因此g[i][j]必须为列表
g = defaultdict(lambda: defaultdict(list))  
line_id = defaultdict(dict)


class Edge:
    def __init__(self, weight, line_id):
        self.weight = weight
        self.line_id = line_id


def dijkstra(start, end):
    pre = {}
    info = {}
    dist = defaultdict(lambda: float('inf'))
    cnt = defaultdict(lambda: 0)
    st = defaultdict(lambda: False)
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))
    while heap:
        t = heapq.heappop(heap)
        distance = t[0]
        ver = t[1]
        if ver == end:
            break
        if st[ver]:
            continue
        st[ver] = True

        for y in g[ver]:
            li = g[ver][y]
            for i in range(len(li)):
                if dist[y] > distance + li[i].weight:
                    dist[y] = distance + li[i].weight
                    cnt[y] = cnt[ver] + 1
                    pre[y] = ver
                    heapq.heappush(heap, (dist[y], y))
                    info[y] = "Take Line#{} from {} to {}.".format(li[i].line_id, ver, y)
                elif dist[y] == distance + li[i].weight and cnt[ver] + 1 < cnt[y]:
                    cnt[y] = cnt[ver] + 1
                    pre[y] = ver
                    info[y] = "Take Line#{} from {} to {}.".format(li[i].line_id, ver, y)

    print(dist[end])
    path = []
    i = end
    while i != start:
        path.append(info[i])
        i = pre[i]

    path = path[::-1]

    for x in path:
        print(x)


n = int(input())

for i in range(1, n + 1):
    stops = input().split()[1:]
    m = len(stops)
    for j in range(m):
        for k in range(j):
            if stops[0] == stops[m - 1]:
                length = min(j - k, m - 1 - (j - k))
            else:
                length = j - k
            g[stops[j]][stops[k]].append(Edge(length, i))
            g[stops[k]][stops[j]].append(Edge(length, i))

k = int(input())

while k > 0:
    k -= 1
    start, end = input().split()
    dijkstra(start, end)