题解 | #最优乘车#

题目链接

最优乘车

题目描述

给定一个城市的公交网络，包含若干个站点和若干条单向公交线路。每条线路都按顺序经过一系列站点。乘客可以在任意站点换乘。求从1号站到N号站的最少换乘次数。

解题思路

这是一个典型的图论建模和最短路径问题。问题的关键在于如何定义图的节点和边，以使“最少换乘次数”这个目标能够通过标准算法求解。

图的建模

我们可以将问题转化为求解一个无权图的单源最短路径。

转化目标：最少换乘次数等价于乘坐最少的公交线路数。如果乘坐了 $k$ 条线路，那么换乘次数就是 $k-1$ 。因此，我们的目标是找到一条使用最少公交线路从起点到终点的路径。
节点 (Vertices)：图中的节点可以直接对应为公交站点。
边 (Edges)：边的定义是核心。我们希望图中的一条边代表“一次乘车”，即乘坐一条公交线路从一个站到另一个站。因此，我们可以这样构建图：对于每一条公交线路，如果该线路可以从站点 $u$ 到达站点 $v$ （ $u$ 在 $v$ 之前），我们就在图中添加一条从 $u$ 到 $v$ 的有向边。
模型总结：在这个构建出的图中，任意一条路径的长度（经过的边数）就等于乘坐的公交线路数量。问题就变成了在这个无权图上寻找从节点1到节点N的最短路径。

算法选择

对于求解无权图的单源最短路径问题，广度优先搜索 (BFS) 是最适合且最高效的算法。BFS能够保证找到从起点到其他所有节点的最少边数。

算法流程

建图：
- 使用一个二维数组（邻接矩阵）adj[i][j] 来表示站点 $i$ 和 $j$ 是否可以通过单次乘车直接到达。
- 读取所有公交线路。对于每条线路上的站点序列，例如 $\{s_1, s_2, \dots, s_k\}$ ，我们为所有 $i < j$ 的组合，在图中添加边 $(s_i, s_j)$ ，即设置 adj[s_i][s_j] = true。
执行 BFS：
- 创建一个距离数组 dist，其中 dist[i] 记录从1号站到 $i$ 号站最少需要乘坐的线路数。初始化所有值为-1（表示不可达）。
- 创建一个队列 q，将起点1入队，并设置 dist[1] = 0。
- 当队列不为空时，取出队首站点 u。遍历所有站点 v，如果存在从 u到v的边（即adj[u][v]为真）且 v 未被访问过（dist[v] == -1），则更新 dist[v] = dist[u] + 1，并将 v 入队。
计算结果：
- BFS结束后，dist[N] 就代表了到达终点所需的最少线路数。
- 如果 dist[N] 为-1，则表示无法到达，输出 NO。
- 否则，最少换乘次数为 dist[N] - 1。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

const int MAXN = 505;
bool adj[MAXN][MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m, n;
    cin >> m >> n;
    cin.ignore(); 

    for (int i = 0; i < m; ++i) {
        int k;
        cin >> k;
        vector<int> stops(k);
        for(int j = 0; j < k; ++j) {
            cin >> stops[j];
        }

        for (int u_idx = 0; u_idx < k; ++u_idx) {
            for (int v_idx = u_idx + 1; v_idx < k; ++v_idx) {
                adj[stops[u_idx]][stops[v_idx]] = true;
            }
        }
    }

    vector<int> dist(n + 1, -1);
    queue<int> q;

    dist[1] = 0;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u == n) {
            break; 
        }

        for (int v = 1; v <= n; ++v) {
            if (adj[u][v] && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    if (dist[n] == -1) {
        cout << "NO" << endl;
    } else {
        cout << dist[n] - 1 << endl;
    }

    return 0;
}

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        boolean[][] adj = new boolean[n + 1][n + 1];

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            int[] stops = new int[k];
            for (int j = 0; j < k; j++) {
                stops[j] = Integer.parseInt(st.nextToken());
            }

            for (int u_idx = 0; u_idx < k; u_idx++) {
                for (int v_idx = u_idx + 1; v_idx < k; v_idx++) {
                    adj[stops[u_idx]][stops[v_idx]] = true;
                }
            }
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();

        dist[1] = 0;
        q.offer(1);

        while (!q.isEmpty()) {
            int u = q.poll();

            if (u == n) {
                break;
            }

            for (int v = 1; v <= n; v++) {
                if (adj[u][v] && dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.offer(v);
                }
            }
        }

        if (dist[n] == -1) {
            System.out.println("NO");
        } else {
            System.out.println(dist[n] - 1);
        }
    }
}

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    try:
        m, n = map(int, input().split())
    except ValueError:
        return # Handle empty input

    adj = [[False] * (n + 1) for _ in range(n + 1)]

    for _ in range(m):
        # First line of pair is k, which we don't need directly
        # Second line is the stops
        stops_line = input()
        if not stops_line: continue
        parts = list(map(int, stops_line.split()))
        k = parts[0]
        stops = list(map(int, input().split()))
        
        for i in range(len(stops)):
            for j in range(i + 1, len(stops)):
                u, v = stops[i], stops[j]
                adj[u][v] = True
    
    dist = [-1] * (n + 1)
    q = deque()

    if n == 1:
        print(0)
        return

    dist[1] = 0
    q.append(1)

    while q:
        u = q.popleft()
        if u == n:
            break
        
        for v in range(1, n + 1):
            if adj[u][v] and dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    
    if dist[n] == -1:
        print("NO")
    else:
        print(dist[n] - 1)

if __name__ == "__main__":
    main()

算法及复杂度

算法：图论建模 + 广度优先搜索 (BFS)
时间复杂度： $O(\sum L_i^2 + N^2)$ ，其中 $L_i$ 是第 $i$ 条线路的站点数， $N$ 是总站点数。建图的时间复杂度为 $\sum O(L_i^2)$ ，BFS 在邻接矩阵上的时间复杂度为 $O(N^2)$ 。
空间复杂度： $O(N^2)$ ，主要用于存储邻接矩阵。