Submission #423445

---

Source Code Expand

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[] from = new int[M];
		int[] to   = new int[M];
		int[] time = new int[M];

		for(int i=0;i<M;i++){
			from[i] = sc.nextInt()-1;
			to[i]   = sc.nextInt()-1;
			time[i]= sc.nextInt();
		}
		int[][] map = new int[N][N];

		for(int i=0;i<M;i++){
			map[from[i]][to[i]] = time[i];
			map[to[i]][from[i]] = time[i];
		}

		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				if(map[i][j]==0){
					map[i][j]=9999;
				}
			}
		}

		for(int k=0;k<N;k++){
			for(int i=0;i<N;i++){
				for(int j=0;j<N;j++){
					map[i][j] = Math.min(map[i][j],map[i][k]+map[k][j]);
				}
			}
		}

		int[] badcase = new int[N];
		for(int i=0;i<N;i++){
			int MAX = 0;
			for(int j=0;j<N;j++){
				if(map[i][j] > MAX && i!=j){
					MAX = map[i][j];
				}
			}
			badcase[i] = MAX;
		}

		int MIN = 9999;
		for(int i=0;i<N;i++){
			if(badcase[i] < MIN){
				MIN = badcase[i];
			}
		}
		System.out.println(MIN);
		}

	}

Submission Info

Judge Result