题面描述

在这个问题中，给定多条地铁线路，包括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);
}

题目内容

有若干个地铁线路。所有地铁线路分为$L$形线和$O$形线

$L$形线有两个端点，在端点处的站点只能往另外一端移动，在非端点处则有两个移动方向可选择。

$O$形线也称$O$线，没有端点，在任一站都有两个移动方向可选择。

所有地铁站线中有以下两种移动方式：

1. 从一个线路中的一个站移动到当前线路的另一个站点
2. 从一个线路中的一个站点跳跃到另一条绳子的另一个站点

所有n个站点都被编号，从1到n，选择其中一个作为起点，再选择另一个作为终点。

一次输入一条线路上所有结的编号：例如{$1$，$5$}，表示一条$L$形线路，两端为$1$，$5$。例如{$1$，$2$，$3$，$4$，$1$}，表示一条$O$形线路。这两条线路在$1$这个站点允许从一条线路跳到另一条线路的站点上，即可以从$L$形线路的$1$站点跳到$O$形线路的$2$站点，也可以从$O$形线路的$1$站点跳到$L$形线路的$5$站点。

规定了一系列输出：

1. 最短跳跃路线数目:满足最短路线长度要求的所有路线的数目
2. 最短跳跃路线长度（不计算起点）
3. 最优跳跃路线数目:满足最短跳跃路线长度要求的跨绳跳跃次数最少的路线的数目

解答要求

时间限制: $C/C++ 1000ms$,其他语言: $2000ms$ 内存限制:$C/C++256MB$其他语言:$512MB$

输入

第一行:第一个正整数$M$，表示地铁线路的条数$M$，$M$的范围是[$1，500$]。

第二行:列出$M$条地铁线路的站点数$N(1)，N(2)，...，N(M)$，用空格分隔，注意，$0$形线的首尾各算一个站点，例[$1,3,6,7,4,1$]，站点数$N$记为$6$。

第三行到第$M+2$行:列出$M$条地铁线路的站点信息，站京$ID$用空格分隔，站点数的范围是[$1,2000$]，站点$ID$是$32$位正整数。

第$M+3$行:列出起点和终点，用空格分隔，如果起点或终点不在$M$条地铁线路上，或者，起点和终点是同一个站点时，则认为不存在最短路线。

输出

第一行:输出最短移动路线的数目。注意:如果不存在最短移动路线，则输出$-1$

第二行:输出最短移动路线长度，注意:如果不存在最短移动路线，则输出$-1$。

第三行:输出最优移动路线的数目。注意:如果不存在最优移动路线，则输出$0$。

样例

输入

1
3
1 3 1
1 3

输出

1
1
1

解释

1. 最短线路有$1$条：{$1, 3$}
2. 根据$1$的结果，最短线路线长度是$1$
3. 最优路线有$1$条：{$1, 3$}

样例2

输入

4
5 5 3 2
1 2 3 4 5
1 10 9 7 6
5 7 8
11 5
1 11

输出

2
5
1

解释

1. 最短路线有$2$条，分别是{$1，2，3，4，5，11$}和{$1，10，9，7，5，11$}
2. 根据$1$的结果，最短路线长度是$5$
3. 最优路线有$1$条:{$1，2，3，4，5，11$} (换乘一次)