题解 | 【模板】单源最短路1

import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别

        String s = in.nextLine();
        String[] first = s.split(" ");
        int a = Integer.parseInt(first[0]);
        int b = Integer.parseInt(first[1]);
        int[][] dataRes = new int[5001][5001];
        for (int i = 0; i < b; i++) {
            String next = in.nextLine();
            String[] split = next.split(" ");
            dataRes[Integer.parseInt(split[0])][Integer.parseInt(split[1])] = 1;
            dataRes[Integer.parseInt(split[1])][Integer.parseInt(split[0])] = 1;
        }

        int[] length = new int[5001];
        Arrays.fill(length, 5001);
    
        for (int i = 1; i <= 5000; i++) {
            if (dataRes[1][i] != 0) {
                length[i] = 1;
            }
        }

        boolean[] visit = new boolean[5001];
        visit[1] = true;
        for (int i = 1; i < 5000; i++) {
            int key = 0;
           int min = 5001;
            for (int index = 1; index <= 5000; index++) {
                if (!visit[index] && length[index] < min) {
                    key = index;
                    min = length[index];
                }
            }
            if(key == 0) {
                break;
            }
            visit[key] = true;
            for (int j = 1; j <= 5000; j++) {
                if ( dataRes[key][j] != 0 && length[j]  > min + 1 ) {
                    length[j] = length[key] + 1;
                }
            }
        }
        System.out.println(length[a] > 5000 ? -1 : length[a]);
    }

}