50 lines
1.5 KiB
Java
50 lines
1.5 KiB
Java
import java.util.*;
|
|
|
|
public class _1389 {
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
String[] input = sc.nextLine().split(" ");
|
|
int N = Integer.parseInt(input[0]);
|
|
int M = Integer.parseInt(input[1]);
|
|
|
|
int[][] distance = new int[N+1][N+1];
|
|
for(int i=0; i<M; i++){
|
|
String[] linked_input = sc.nextLine().split(" ");
|
|
int a = Integer.parseInt(linked_input[0]);
|
|
int b = Integer.parseInt(linked_input[1]);
|
|
distance[a][b] = 1;
|
|
distance[b][a] = 1;
|
|
}
|
|
sc.close();
|
|
|
|
int maxValue = 1000000;
|
|
for(int i=1; i<=N; i++){
|
|
for(int j=1; j<=N; j++){
|
|
if(i==j) distance[i][j] = 0;
|
|
else if(distance[i][j] == 0) distance[i][j] = maxValue;
|
|
}
|
|
}
|
|
|
|
for(int k=1; k<=N; k++){
|
|
for(int i=1; i<=N; i++){
|
|
for(int j=1; j<=N; j++){
|
|
distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
|
|
}
|
|
}
|
|
}
|
|
|
|
int[] result = new int[N+1];
|
|
int minDistance = maxValue;
|
|
int result_person = 0;
|
|
for(int i=1; i<=N; i++){
|
|
for (int j = 1; j <= N; j++) {
|
|
result[i] += distance[i][j];
|
|
}
|
|
if(minDistance>result[i]){
|
|
result_person = i;
|
|
minDistance = result[i];
|
|
}
|
|
}
|
|
System.out.println(result_person);
|
|
}
|
|
} |