$$\color{Red}{最优乘车——【线路型建图转化节点图】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

解析

这道题难点不在于选什么算法，其实这道题数据量 n <= 100，选最坏的代码最少的多源最短路 floyd ，也只需要最坏的情况下为 1 * 10 ^ 6，可以在 1秒内ac。

一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，代码中的操作次数控制在 10 ^ 7 ∼ 10 ^ 8 为最佳。

n <= 100 -> O(n ^ 3) -> 状态压缩dp floyd 高斯消元

n <= 1000 -> O(n ^ 2) O(n ^ 2 * log(n)) -> dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford

n ≤ 100000 -> O(nlogn) -> 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa

思路

这道题的难点在于建图，最开始的直觉思想，可能是要用搜索，但是要多开一个状态数组，存当前到这个节点的是第几次换乘，但是为了存这个，还得用一个状态记录当前是在哪条线路。感觉复杂度大大提高。

而y总提供了一个这种路线题换乘的建图思路 ------> 一条路线为一个单向图，我们建图的时候，前面的节点同时对后面的所有节点建立一个边权为1的边，这样即做到了同一条线路，坐车到达其中后面站点任何一个节点，我们只用坐一次车。

此时我们只需要使用bfs即可找寻最优解，而题目保证 n >= 2,故起点终点相同的边界条件不用考虑，那么换乘数显然就是乘车数 - 1。

当然既然边权为1，没必要开 int数组，每个数据需要 4 字节，开boalean数组，每个数据只有 1字节，大大节省空间。

我的SPFA全题解

我的Dijkstra全题解

我的Bellman_fold全题解

我的Floyd全题解

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;


/**
 * @author Fanxy
 */
public class Main {

    private static final int INF = 0x3f3f3f3f;
    static int n, m, N = 510;
    static boolean[][] g = new boolean[N][N];
    static int[] d = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static void bfs() {
        Arrays.fill(d, INF);
        d[1] = 0;
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(1);
        while (!queue.isEmpty()) {
            Integer top = queue.remove();
            for (int i = 1; i <= n; i++) {
                if (g[top][i] && d[i] > d[top] + 1){
                    d[i] = d[top] + 1;
                    queue.add(i);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        String[] s1 = br.readLine().split(" ");
        m = Integer.parseInt(s1[0]);
        n = Integer.parseInt(s1[1]);
        while (m-- > 0) {
            String[] s2 = br.readLine().split(" ");
            int len = s2.length;
            for (int i = 0; i < len; i++) {
                for (int j = i + 1; j < len; j++) {
                    g[Integer.parseInt(s2[i])][Integer.parseInt(s2[j])] = true;
                }
            }
        }
        bfs();
        if (d[n] == INF) System.out.println("NO");
        else System.out.println(d[n] - 1);
    }
}