思路

如果用常规的图的存储，需要判断该点是从哪个线路来的，比较的麻烦。
通过添加边的方式，即给每个能连通的点都添加一条边的方式，来建立图。
这样的好处的是，能将题目转化为两个关键字的最短路问题。
题目中所求的最短路径相同时，换乘最少。在新的建图方式下，就转化为求最短路径相同时，求边数最少的。

关键点：
1. 通过对最坏情况下点数和边数的估计，选择邻接表存储图。
添加边时，需要考虑回路和非回路的区别，如果是回路选择走最短距离的方向。
2. dij函数的实现，需要堆优化。

注意：
站点编号不足4位时，需要在前面添0.

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

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

int n;
int h[N], e[M], ne[M], line[M], w[M], idx;
int dist[N], stops[N], pre[N] ,cnt[N];
bool st[N];
string info[N]; //记录换乘信息 

void add(int a, int b, int c, int d) {
    e[idx] = b, w[idx] = c, line[idx] = d, ne[idx] = h[a], h[a] = idx++;
}

string format(int x) {
    char num[10];
    sprintf(num, "%04d", x);
    return num;
}

void dijkstra(int S, int T) {
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0x3f, sizeof cnt);
    memset(st, 0, sizeof st);

    dist[S] = cnt[S] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, S});

    while (heap.size()) {
        auto t = heap.top();
        heap.pop();

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

        for (int i = h[ver]; ~i; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i]) {
                dist[j] = dist[ver] + w[i];
                cnt[j] = cnt[ver];
                pre[j] = ver; 
                info[j] = "Take Line#"+ to_string(line[i]) 
                +" from "+ format(ver) + " to " + format(j) + ".";
                heap.push({dist[j], j});
            } else if (dist[j] == dist[ver] + w[i]) {
                if (cnt[j] > cnt[ver] + 1) {
                    cnt[j] = cnt[ver] + 1;
                    pre[j] = ver; 
                    info[j] = "Take Line#"+ to_string(line[i]) 
                    +" from "+ format(ver) + " to " + format(j) + ".";
                }
            }
        }
    }
    vector<string> res;
    for (int i = T; i != S; i = pre[i]) res.push_back(info[i]);
    cout << dist[T] << '\n';
    for (int i = res.size() - 1; i >= 0; i--) cout << res[i] << '\n';
}

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];

        int len;
        for (int j = 0; j < m; j++)
            for (int k = 0; k < j; k++) {
                if (stops[0] != stops[m - 1]) len = j - k;
                else len = min(j - k, m - 1 - j + k); //回路取路径短的方向 
                add(stops[j], stops[k], len, i);
                add(stops[k], stops[j], len, i);
            }
    } 
    int k;
    cin >> k;
    while (k --) {
        int S, T;
        cin >> S >> T;
        dijkstra(S, T);
    }

    return 0;
}