算法分析

换乘多少次 可以转换为 乘坐过多少次车减1

• 1、在同一条路线中，任意一个在此路线上的车站均能沿着该路线的方向到达后面的车站，权值都是1，表示只乘坐一次车

• 2、通过建图，由于权值均是1，使用bfs求出1号点到n号点最少乘过多少次车

时间复杂度$O(M*N^2)$

假设1条路线经过所有的站，则边数为$(N - 1) + (N - 2) + … + 1 = N * (N - 1) / 2$

题目共有M条，因此运行的最多次数是$M * N * (N - 1) / 2$

因此时间复杂度是 $O(M*N^2)$

参考文献

Java 代码

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

public class Main{
    static int N = 510;
    static int m;
    static int n;
    static boolean[][] g = new boolean[N][N];
    static int[] stop = new int[N];
    static int[] dist = new int[N];
    static void bfs()
    {
        Queue<Integer> q = new LinkedList<Integer>();
        Arrays.fill(dist, -1);
        q.add(1);
        dist[1] = 0;
        while(!q.isEmpty())
        {
            int t = q.poll();
            for(int i = 1;i <= n;i ++)
            {
                if(dist[i] != -1) continue;
                if(!g[t][i]) continue;
                dist[i] = dist[t] + 1;
                q.add(i);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        m = Integer.parseInt(s1[0]);
        n = Integer.parseInt(s1[1]);
        while(m -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            for(int i = 0;i < s2.length;i ++)
            {
                stop[i] = Integer.parseInt(s2[i]);
            }
            for(int i = 0;i < s2.length - 1;i ++)
                for(int j = i + 1;j < s2.length;j ++)
                    g[stop[i]][stop[j]] = true;
        }

        bfs();
        //若不能到达
        if(dist[n] == -1) System.out.println("NO");
        else System.out.println(dist[n] - 1);
    }
}