【图】最短路径之旅游规划（java实现）某国准备选择新的首都，并对新首都的位置提出要求：即新首都到该国所有其他城市的平均距离最短

某国准备选择新的首都，并对新首都的位置提出要求：即新首都到该国所有其他城市的平均距离最短（当然并不一定要求城市之间直达，间接道路也是允许的，但必须可达）。

已知该国的城市信息，请回答新首都应选择哪一个城市。

输入格式:

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据第一行输入2个整数n和m，表示该国的城市总数以及现有的道路总数（1≤n≤100， 0≤m≤n*(n-1)/2 ），为方便起见，我们规定城市编号为1到n。 接下来输入m行数据，每行3个整数u、v、d（1≤u,v≤n，1≤d≤100），分别代表连接某条道路的两个城市编号以及该道路的长度。

输出格式:

对于每组测试，输出新首都的城市编号，若有多个满足条件的城市，选择编号最小的，若没有城市满足新首都的条件，请输出0。

输入样例:

3
4 5
1 2 10
1 3 20
4 3 5
4 1 7
2 4 8
3 1
1 2 10
5 7
1 2 2
3 2 5
2 5 18
4 2 6
1 3 8
3 4 11
1 4 8

输出样例:

4
0
2

代码如下： 

import java.util.ArrayList;
import java.util.Scanner;
public class Main {  
    public static void main(String[] args) {      
        Scanner sc = new Scanner(System.in); 
        int groupNums = sc.nextInt();//数据的组数       
        for (int i = 0; i < groupNums; i++) {      
            int cityNums = sc.nextInt();//城市总数(顶点总数)   
            int roadNums = sc.nextInt();//道路总数(边的总数)    
            Graph graph = new Graph(cityNums);  
            for (int j = 0; j < roadNums; j++) {   
                int city1 = sc.nextInt();   
                int city2 = sc.nextInt();   
                int roadLength = sc.nextInt();//道路长度(边的权值)
                graph.addWeight(city1 - 1, city2 - 1, roadLength);         
            }   
            graph.begin();          
            if (!graph.isList()) {//不是连通图    
                System.out.println("0");     
            }          
            else {//是连通图     
                int minLength=10000;   
                int minIndex=0;     
                for (int j=0;j vertexList;//储存顶点   
        private int[][] weight;//储存边的权值  
        private boolean[] isVisited;//判断进行深度遍历时,某个结点是否已经被访问过  
        public Graph(int n) {   
            vertexList = new ArrayList<>(n);    
            weight = new int[n][n];       
            isVisited = new boolean[n];    
            for (int i = 0; i < n; i++)   
                vertexList.add(i);        
            for (int i = 0; i < n; i++)   
                isVisited[i] = false;  
        }        
        public void addWeight(int v1, int v2, int weight) {//不存在的权值置为0  
            this.weight[v1][v2] = weight; 
        }        //将没有连通的边的权置为一个较大的数,方便后续算法     
        public void begin() {   
            boolean youxiang=false;  
            for (int i=0;i