题解

题面描述

给定一个城市的地铁网络，由多条地铁线路组成。每条线路由多个车站构成，线路本身没有交叉点。当不同线路在某些车站上共有相同站点时，乘客可以在这些站点之间进行换乘。地铁线路分为两种类型：

1. $I$形线：具有两个端点，乘客在端点处只能乘坐开往另一端的地铁，而在非端点处可以选择两个方向。
2. $O$形线：形成一个环路，没有端点，乘客在任何站点都有两个方向可选。

每个车站由一个唯一的32位正整数ID标识。给定起点和终点，要求计算以下内容：

1. 最短路线数目：从起点到终点经过的最少站数的所有路线的数量。
2. 最短路线长度：最短路线经过的站数（不含起点，含终点）。
3. 最优路线数目：在最短路线中，换乘次数最少的路线的数量。

如果不存在从起点到终点的路径，则输出相应的默认值。

思路

1. 数据建模

将地铁网络建模为一个无向图：

• 节点：每个车站对应图中的一个节点，节点编号为0到$S-1$（$S$为总站点数）。
• 边：如果两个车站在同一条线路上相邻，则在它们之间建立一条无向边。

2. 处理换乘

换乘发生在多个线路共享同一站点的地方。因此，乘客可以在这些站点之间切换线路。在建模时，无需额外处理换乘，只需确保在这些站点之间存在多条线路即可。

3. 最短路径和路径数目

使用广度优先搜索（BFS）来计算从起点到终点的最短路径长度及其路径数目。在BFS过程中，记录每个节点的最短距离和到达该节点的路径数。

4. 最优路径（最少换乘次数）

为了计算最优路径（在最短路径中换乘次数最少的路径），需要在BFS的基础上，进一步记录每条路径的换乘次数。具体步骤如下：

• 状态定义：每个状态包括当前站点和当前线路。
• 记录信息：
  • 对于每个站点和线路，记录到达该站点通过该线路的最短距离、最少换乘次数以及路径数目。
• 转移规则：
  • 从当前状态出发，遍历所有相邻站点。
  • 对于每个相邻站点，检查通过哪条线路连接。
  • 如果继续沿用当前线路，则换乘次数不变；否则，换乘次数加1。
  • 更新到达相邻站点的最短距离和最少换乘次数，并累加路径数目。

5. 处理特殊情况

• 起点或终点不在任何线路上，或者起点和终点相同，输出相应的默认值。

6. 避免重复计数

确保在计算路径数目时，不因线路的双向性或环路而导致重复计数。每条路线应被唯一地识别和计数。

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 结构体用于记录站点的信息
struct Station {
    ll id;
    vector<int> lines; // 所属线路
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int M;
    cin >> M;
    
    vector<int> N(M);
    for(auto &x: N) cin >> x;
    
    // 站点ID到索引的映射
    unordered_map<ll, int> id_map;
    vector<Station> stations;
    int station_count = 0;
    
    // 存储每条线路的站点序列
    vector<vector<int>> lines(M);
    
    for(int i=0;i<M;i++){
        lines[i].reserve(N[i]);
        for(int j=0; j<N[i]; j++){
            ll tmp;
            cin >> tmp;
            if(id_map.find(tmp) == id_map.end()){
                id_map[tmp] = station_count;
                stations.push_back(Station{tmp, {}});
                station_count++;
            }
            int idx = id_map[tmp];
            lines[i].push_back(idx);
            stations[idx].lines.push_back(i);
        }
    }
    
    ll start_id, end_id;
    cin >> start_id >> end_id;
    
    // 检查起点和终点是否存在且不同
    if(id_map.find(start_id) == id_map.end() || id_map.find(end_id) == id_map.end() || start_id == end_id){
        cout << "0\n-1\n0";
        return 0;
    }
    
    int start = id_map[start_id];
    int end = id_map[end_id];
    
    // 构建邻接表
    vector<vector<int>> adj(station_count, vector<int>());
    for(int i=0;i<M;i++){
        for(int j=0; j<lines[i].size()-1; j++){
            adj[lines[i][j]].push_back(lines[i][j+1]);
            adj[lines[i][j+1]].push_back(lines[i][j]);
        }
        // 不为O形线添加额外的自环边
    }
    
    // BFS计算最短路径和路径数
    vector<int> distance_vec(station_count, -1);
    vector<long long> path_count(station_count, 0);
    queue<int> q;
    q.push(start);
    distance_vec[start] = 0;
    path_count[start] = 1;
    
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(auto &v: adj[u]){
            if(distance_vec[v] == -1){
                distance_vec[v] = distance_vec[u] +1;
                path_count[v] = path_count[u];
                q.push(v);
            }
            else if(distance_vec[v] == distance_vec[u] +1){
                path_count[v] += path_count[u];
            }
        }
    }
    
    if(distance_vec[end] == -1){
        cout << "0\n-1\n0";
        return 0;
    }
    
    // 输出最短路径数和长度
    cout << path_count[end] << "\n" << distance_vec[end] << "\n";
    
    // 计算最优路径（最少换乘）
    // 使用BFS，同时跟踪每个站点的最短距离、最少换乘次数和路径数
    // 定义结构体记录每个状态
    struct State {
        int station;
        int transfers;
    };
    
    // 初始化
    vector<int> min_transfers(station_count, INT32_MAX);
    vector<long long> optimal_paths(station_count, 0);
    queue<State> qq;
    qq.push(State{start, 0});
    min_transfers[start] = 0;
    optimal_paths[start] = 1;
    
    while(!qq.empty()){
        State current = qq.front(); qq.pop();
        int u = current.station;
        int trans = current.transfers;
        for(auto &v: adj[u]){
            // 计算从u到v是否需要换乘
            // 判断是否存在至少一条共同线路
            bool has_common_line = false;
            for(auto &line_u: stations[u].lines){
                for(auto &line_v: stations[v].lines){
                    if(line_u == line_v){
                        has_common_line = true;
                        break;
                    }
                }
                if(has_common_line) break;
            }
            int new_trans = trans;
            if(!has_common_line){
                new_trans +=1; // 换乘
            }
            // 更新最少换乘次数和路径数
            if(distance_vec[v] == distance_vec[u] +1){
                if(new_trans < min_transfers[v]){
                    min_transfers[v] = new_trans;
                    optimal_paths[v] = optimal_paths[u];
                    qq.push(State{v, new_trans});
                }
                else if(new_trans == min_transfers[v]){
                    optimal_paths[v] += optimal_paths[u];
                }
            }
        }
    }
    
    // 找到最少换乘次数下的路径数
    cout << optimal_paths[end];
    
    return 0;
}

python

from collections import defaultdict, deque
import sys

def main():
    M = int(sys.stdin.readline())
    N = list(map(int, sys.stdin.readline().split()))
    
    id_map = dict()
    stations = []
    station_count = 0
    lines = []
    
    for i in range(M):
        line_ids = list(map(int, sys.stdin.readline().split()))
        line = []
        for id in line_ids:
            if id not in id_map:
                id_map[id] = station_count
                stations.append({'id': id, 'lines': []})
                station_count +=1
            idx = id_map[id]
            line.append(idx)
            stations[idx]['lines'].append(i)
        lines.append(line)
    
    start_id, end_id = map(int, sys.stdin.readline().split())
    
    if start_id not in id_map or end_id not in id_map or start_id == end_id:
        print(0)
        print(-1)
        print(0)
        return
    
    start = id_map[start_id]
    end = id_map[end_id]
    
    # 构建邻接表
    adj = [[] for _ in range(station_count)]
    for i in range(M):
        for j in range(len(lines[i])-1):
            adj[lines[i][j]].append(lines[i][j+1])
            adj[lines[i][j+1]].append(lines[i][j])
        # 不为O形线添加额外的自环边
    
    # BFS计算最短路径和路径数
    distance = [-1]*station_count
    path_count = [0]*station_count
    q = deque()
    q.append(start)
    distance[start] =0
    path_count[start] =1
    
    while q:
        u = q.popleft()
        for v in adj[u]:
            if distance[v] == -1:
                distance[v] = distance[u]+1
                path_count[v] = path_count[u]
                q.append(v)
            elif distance[v] == distance[u]+1:
                path_count[v] += path_count[u]
    
    if distance[end] == -1:
        print(0)
        print(-1)
        print(0)
        return
    
    print(path_count[end])
    print(distance[end])
    
    # 计算最优路径（最少换乘）
    # 使用BFS，同时跟踪每个站点的最短距离、最少换乘次数和路径数
    min_transfers = [float('inf')]*station_count
    optimal_paths = [0]*station_count
    qq = deque()
    qq.append((start, 0))
    min_transfers[start] = 0
    optimal_paths[start] = 1
    
    while qq:
        u, trans = qq.popleft()
        for v in adj[u]:
            # 判断是否需要换乘
            has_common_line = False
            for line_u in stations[u]['lines']:
                for line_v in stations[v]['lines']:
                    if line_u == line_v:
                        has_common_line = True
                        break
                if has_common_line:
                    break
            new_trans = trans
            if not has_common_line:
                new_trans +=1
            # 更新最少换乘次数和路径数
            if distance[v] == distance[u] +1:
                if new_trans < min_transfers[v]:
                    min_transfers[v] = new_trans
                    optimal_paths[v] = optimal_paths[u]
                    qq.append((v, new_trans))
                elif new_trans == min_transfers[v]:
                    optimal_paths[v] += optimal_paths[u]
    
    print(optimal_paths[end])

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    static class Station {
        long id;
        List<Integer> lines;
        Station(long id){
            this.id = id;
            lines = new ArrayList<>();
        }
    }
    
    static class State {
        int station;
        int transfers;
        State(int s, int t){
            station = s;
            transfers = t;
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        String[] N_str = br.readLine().split(" ");
        int[] N = new int[M];
        for(int i=0;i<M;i++) N[i] = Integer.parseInt(N_str[i]);
        
        Map<Long, Integer> id_map = new HashMap<>();
        List<Station> stations = new ArrayList<>();
        int station_count =0;
        List<List<Integer>> lines = new ArrayList<>();
        for(int i=0;i<M;i++) lines.add(new ArrayList<>());
        
        for(int i=0;i<M;i++){
            String[] ids = br.readLine().split(" ");
            for(int j=0; j<N[i]; j++){
                long id = Long.parseLong(ids[j]);
                if(!id_map.containsKey(id)){
                    id_map.put(id, station_count);
                    stations.add(new Station(id));
                    station_count++;
                }
                int idx = id_map.get(id);
                lines.get(i).add(idx);
                stations.get(idx).lines.add(i);
            }
        }
        
        String[] se = br.readLine().split(" ");
        long start_id = Long.parseLong(se[0]);
        long end_id = Long.parseLong(se[1]);
        
        if(!id_map.containsKey(start_id) || !id_map.containsKey(end_id) || start_id == end_id){
            System.out.println("0");
            System.out.println("-1");
            System.out.println("0");
            return;
        }
        
        int start = id_map.get(start_id);
        int end = id_map.get(end_id);
        
        // 构建邻接表
        List<List<Integer>> adj = new ArrayList<>();
        for(int i=0;i<station_count;i++) adj.add(new ArrayList<>());
        for(int i=0;i<M;i++){
            for(int j=0; j<lines.get(i).size()-1; j++){
                int u = lines.get(i).get(j);
                int v = lines.get(i).get(j+1);
                adj.get(u).add(v);
                adj.get(v).add(u);
            }
            // 不为O形线添加额外的自环边
        }
        
        // BFS计算最短路径和路径数
        int[] distance = new int[station_count];
        Arrays.fill(distance, -1);
        long[] path_count = new long[station_count];
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        distance[start] =0;
        path_count[start] =1;
        
        while(!q.isEmpty()){
            int u = q.poll();
            for(int v: adj.get(u)){
                if(distance[v] == -1){
                    distance[v] = distance[u]+1;
                    path_count[v] = path_count[u];
                    q.add(v);
                }
                else if(distance[v] == distance[u]+1){
                    path_count[v] += path_count[u];
                }
            }
        }
        
        if(distance[end] == -1){
            System.out.println("0");
            System.out.println("-1");
            System.out.println("0");
            return;
        }
        
        System.out.println(path_count[end]);
        System.out.println(distance[end]);
        
        // 计算最优路径（最少换乘）
        // 使用BFS，同时跟踪每个站点的最短距离、最少换乘次数和路径数
        int[] min_transfers = new int[station_count];
        Arrays.fill(min_transfers, Integer.MAX_VALUE);
        long[] optimal_paths = new long[station_count];
        Queue<State> qq = new LinkedList<>();
        qq.add(new State(start, 0));
        min_transfers[start] = 0;
        optimal_paths[start] = 1;
        
        while(!qq.isEmpty()){
            State current = qq.poll();
            int u = current.station;
            int trans = current.transfers;
            for(int v: adj.get(u)){
                // 判断是否需要换乘
                boolean has_common_line = false;
                for(int line_u: stations.get(u).lines){
                    for(int line_v: stations.get(v).lines){
                        if(line_u == line_v){
                            has_common_line = true;
                            break;
                        }
                    }
                    if(has_common_line) break;
                }
                int new_trans = trans;
                if(!has_common_line){
                    new_trans +=1;
                }
                // 更新最少换乘次数和路径数
                if(distance[v] == distance[u] +1){
                    if(new_trans < min_transfers[v]){
                        min_transfers[v] = new_trans;
                        optimal_paths[v] = optimal_paths[u];
                        qq.add(new State(v, new_trans));
                    }
                    else if(new_trans == min_transfers[v]){
                        optimal_paths[v] += optimal_paths[u];
                    }
                }
            }
        }
        
        System.out.println(optimal_paths[end]);
    }
}

题目内容

城市的地铁网络由多条线路组成，每条线路上有多个车站，线路自身没有交叉点。线路间交叉或重叠时，共用车站，在这些车站上可相互换乘，每条线路都是双向行车。

线路有两种:$I$形线和$O$形线

$I$形线有两个端点，乘客在端点处只能乘坐开往另外一端的地铁，在非端点处则有两个方向可选择。

$O$形线所有车站形成环，没有端点，乘客在任一站都有两个方向可选择。

在地铁网络中任选一站为起点，任选另一站为终点，中途可换乘，地铁网络中的每一个站点用一个唯一的$ID$标识，$ID$是一个$32$位正整数。一次输入一条线路，线路表示为一个站点$ID$数组;

例如{$2,3,6,9, 10$},表示这是一条$I$形线，$2$和$10$为两端;

例如{$1,3,6,7,4,1$}，首尾站点一样，表示这是一条$O$形线; 两条线路中出现了相同站点(如上面的$3、6$)，表示两条线路在这些站点可相互换乘。

最短路线长度定义为从起点到终点经过的最少站数(站数计算不含起点,含终点).

要求输出

1)最短路线数目:满足最短路线长度要求的所有路线的数目

2)最短路线长度

3)最优路线数目:满足最短路线长度要求的换乘次数最少的路线的数 目

输入描述

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

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

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

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

输出描述

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

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

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

样例1

输入

1
5
1 2 3 4 1
1 3

输出

2
2
2

说明

$1)$最短路线有2条:{$1，2，3$}，{$1,4,3$}

$2)$根据$1$的结果，最短路线长度是$2$

$3)$最优路线有$2$条:{$1,2,3$}，{$1，4，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$}(换乘一次)