最小转机

coding>Java
1k 词

题目描述

小哼和小哈一同坐飞机旅游，他们现在位于1号城市，目标是5号城市，可是1号城市并没有到5号城市的直航。不过小哼已经收集了很多航班信息，现在小哼希望找到一种乘坐方式使得转机的次数最少，如何解决呢？

输入

多组输入。

第一行输入n , m , start , end , 其中n表示城市数，m表示航线数，start表示起点城市，end 表示终点城市。紧接着输入m行，每行是一条类似a b这样的数据表示城市a和城市b之间有航线，也就是说城市a和城市b之间可以互相到达。

输出

输出最少转机数,若不能到达请输出”Cannot reach”。

样例输入

1
2
3
4
5
6
7
8
5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5

样例输出

1
2

提示

起终点为0时不可达

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Scanner;
public class Main {
    private static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        int start = input.nextInt();
        int end = input.nextInt();
        int[][] edge = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++) 
                edge[i][j] = INF;
        while (m-- > 0) {
            int a = input.nextInt();
            int b = input.nextInt();
            edge[a][b] = 1;
            edge[b][a] = 1;
        }
        for (int k = 1; k <= n; k++) 
            for (int i = 1; i <= n; i++) 
                for (int j = 1; j <= n; j++) 
                    if (edge[i][k] != INF && edge[k][j] != INF) 
                        edge[i][j] = Math.min(edge[i][j], edge[i][k] + edge[k][j]);
        System.out.println(edge[start][end]);
        input.close();
    }
}