题面描述

在这个问题中，给定多条地铁线路，包括L形和O形，要求计算从起点到终点的最短移动路线数量、最短路线长度以及最优移动路线数量。输入包括线路数量、每条线路的站点信息及起止站编号。输出分别为最短路线的数量、长度，以及最优路线的数量。如果没有可行路线，分别输出-1或0。

思路

解题思路是通过构建邻接表表示地铁线路的节点关系，并使用广度优先搜索（BFS）算法寻找起点到终点的最短路径。BFS能够保证找到无权图中的最短路径，并在遍历过程中统计路径数量。

在地铁线路的设计中，O形线路和L形线路具有不同的特性和适用场景，这些特性影响了路径搜索和计算的复杂性。下面讨论这两种线路的主要情况和差异：

O形线路（环形线路）

1. 结构特征：

   • O形线路是一个闭环，没有明确的起点和终点，任意两个站点之间都可以直接到达。
   • 在任一站点，乘客可以向两个方向移动，增加了线路的灵活性。

2. 路径计算：

   • 在O形线路上，路径计算相对简单，因为任意两个站点之间的最短路径只需要考虑顺时针和逆时针两种方向。
   • 由于是环形结构，从一个点出发，最短路径可以通过简单的加法来计算（例如，顺时针的站点数和逆时针的站点数）。

3. 跳跃与换乘：

   • 跳跃到其他线路时，乘客可以从任何站点直接跳跃到其他线路的任意站点，给了乘客更多的选择。

L形线路（线形线路）

1. 结构特征：

   • L形线路有两个端点，站点只能在端点处进行单向移动，而在中间站点可以双向移动。
   • 这种结构限制了某些站点之间的直接移动，特别是从端点出发时。

2. 路径计算：

   • 对于L形线路，路径计算稍显复杂，因为从端点到达中间站点后，可以选择两个方向，必须考虑每个站点的前后关系。
   • 从一个端点到另一个端点的路径长度等于通过中间站点的步数，这可能涉及多次换乘。

3. 跳跃与换乘：

   • 从L形线路的任一站点跳跃到其他线路的站点，只有在相应的站点处才可实现，这与O形线路的灵活性相对比显得局限。
   • 在跳跃过程中，L形线路的端点也可能成为换乘的关键节点，影响整体的换乘效率。

总结

O形线路因其环形结构提供了更大的灵活性和更简便的路径计算，而L形线路则具有更严格的路径限制和端点特性。理解这两种线路的不同特性，对于设计最优路径搜索算法至关重要，尤其是在考虑跨线路跳跃和多条线路连接时。

cpp

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, ll>
#define fi first
#define se second
const int N = 2005, M = 505;
​
int n;
vector<int> a[N];       //存每个绳子上的节点
vector<int> e[N];       //存每个节点相邻的节点
pii ans[N];             //存每个节点到起点的最短路和路线数量
bool ee[M][M];      //邻接表存每个绳子之间是否直接相连，用于第三问
vector<int> aa[N];      //存每个节点属于哪些绳子，用于处理出ee
int main()
{
    scanf("%d", &n);
    for(int i = 1 ; i <= n; i ++) {
        int x;
        scanf("%d", &x);
        a[i].resize(x);
    }
    for(int i = 1 ; i <= n ; i ++) {
        int la = -1;
        for(int &t : a[i]) {
            scanf("%d", &t);
            aa[t].push_back(i);
        }
        //如果是只有两个点的O形，就把它看成L形
        if(a[i].size() == 3 && a[i][0] == a[i].back()) {
            a[i].pop_back();
            aa[a[i][0]].pop_back();
        } 
        for(int j = 1 ; j < a[i].size() ; j ++) {
            int x = a[i][j-1], y = a[i][j];
            e[x].push_back(y);
            e[y].push_back(x);
        }
    }
    int st, ed;
    scanf("%d%d", &st, &ed);
    if(st == ed) {
        puts("-1\n-1\n0");
        return 0;
    }
    queue<pii> q;
    q.push({st, 0});
    memset(ans, -1, sizeof ans);
    ans[st] = {0, 1};
    while(q.size()) {
        int t = q.front().fi;
        int p = q.front().se + 1;
        q.pop();
        for(int &g: e[t]) {
            if(ans[g].fi == -1) {
                ans[g] = {p, ans[t].se};
                q.push({g, p});
            } else if(ans[g].fi == p) {
                ans[g].se += ans[t].se;
            }
        }
    }
    printf("%lld\n%d\n", ans[ed].se, ans[ed].fi);
    memset(ans, -1, sizeof ans);
    for(int i = 1 ; i <= 2000 ; i ++) {
        for(int &t: aa[i]) {
            for(int &g: aa[i]) {
                ee[t][g] = true;
            }
        }
    }
    set<int> eed;
    for(int &t: aa[ed]) {
        eed.insert(t);
    }
    for(int &t: aa[st]) {
        q.push({t, 0});
        ans[t] = {0, 1};
        if(eed.count(t)) return puts("1"), 0;
    }
    int mi = -4;
    while(q.size()) {
        int t = q.front().fi;
        int p = q.front().se + 1;
        q.pop();
        for(int g = 1 ; g <= n ; g ++) {
            if(g == t || !ee[t][g]) continue;
            if(ans[g].fi == -1) {
                ans[g] = {p, ans[t].se};
                if(eed.count(g) && mi == -4) mi = p;
                q.push({g, p});
            } else if(ans[g].fi == p) {
                ans[g].se += ans[t].se;
            }
        }
    }
    ll cnt = 0;
    for(const int &t : eed) {
        if(ans[t].fi == mi) cnt += ans[t].se;
    }
    printf("%lld\n", cnt);
}