Floyd算法：
//07-图4 哈利·波特的考试 import java.util.Scanner; class Graph{ private int V; private int E; private int MaxSum = 1000; private int[][] adv; public Graph(int V, int E){ this.V = V; this.E = E; adv = new int[V][V]; } public Graph(Scanner s){ this( s.nextInt(), s.nextInt()); for(int i = 0; i < E; i ++){ int v = s.nextInt(); int w = s.nextInt(); int l = s.nextInt(); addEdge(v, w, l); } for(int i = 0; i < V; i ++){ for(int j = 0; j < V; j ++){ if(i != j && adv[i][j] == 0) addEdge(i + 1, j + 1, MaxSum); } } } public void addEdge(int v, int w, int l){ adv[v - 1][w - 1] = l; adv[w - 1][v - 1] = l; } public int[][] adv(){ return adv; } } public class Main{ static int MaxSum = 1000; static void Floyd(int [][] Dis){ int N = Dis.length; for(int k = 0; k < N; k ++){ for(int i = 0; i < N; i ++){ for(int j = 0; j < N; j ++){ if(Dis[i][j] > Dis[i][k] + Dis[k][j]) Dis[i][j] = Dis[i][k] + Dis[k][j]; } } } } static int findmax(int[] row){ int max = row[0]; for(int n : row){ if(n > max) max = n; } return max; } static void judge(int[][] D){ int min = findmax(D[0]); int index = 0; for(int i = 0; i < D.length; i ++){ if(min > findmax(D[i])) { min = findmax(D[i]); index = i; } } if(min == MaxSum) System.out.println(0); else System.out.println(index + 1 + " " + min); } public static void main(String[] args) { Scanner s = new Scanner(System.in); Graph G = new Graph(s); int[][] Distance = G.adv(); Floyd(Distance); judge(Distance); } }对每个顶点使用Dijkstra算法(由于时间复杂度的原因第四个测试点会运行超时)：
import java.util.Scanner; import java.util.Arrays; class node{ int index; int weigth; node next; } class raph{ private int MaxSum = 1000; private int V; private int E; private node[] nodes; private int[][] D; public raph(int V, int E){ this.V = V; this.E = E; nodes = new node[V]; D = new int[V][V]; for(int[] row : D) Arrays.fill(row, MaxSum); for(int i = 0; i < V; i ++) { nodes[i] = new node(); nodes[i].index = i; } } public raph(Scanner s){ this(s.nextInt(), s.nextInt()); for(int i = 0; i < E; i ++){ int v = s.nextInt(); int w = s.nextInt(); int l = s.nextInt(); addEdge(v - 1, w - 1, l); addEdge(w - 1, v - 1, l); } } void addEdge(int v, int w, int l){ node newnode = new node(); newnode.index = w ; newnode.weigth = l; newnode.next = nodes[v].next; nodes[v].next = newnode; } public int V(){ return V; } public node[] nodes(){ return nodes; } public void Dijkstra(int i){ boolean[] visited = new boolean[V]; D[i][i] = 0; visited[i] = true; for(node n = nodes[i].next; n != null; n = n.next){ D[i][n.index] = n.weigth; //visited[n.index] = true; } while(true){ int index = V; int min = MaxSum; for(int j = 0; j < V; j ++){ if(!visited[j]) { if(min > D[i][j]){ index = j; min = D[i][j]; } } } if(index == V) break; visited[index] = true; for(node n = nodes[index].next; n != null; n = n.next){ if(D[i][n.index] > D[i][index] + n.weigth) D[i][n.index] = D[i][index] + n.weigth; } } } public int[][] D(){ return D; } } public class Main { static int MaxSum = 1000; static int findmax(int[] row){ int max = row[0]; for(int n : row){ if(n > max) max = n; } return max; } static void judge(int[][] D){ int min = findmax(D[0]); int index = 0; for(int i = 0; i < D.length; i ++){ if(min > findmax(D[i])) { min = findmax(D[i]); index = i; } } if(min == MaxSum) System.out.println(0); else System.out.println(index + 1 + " " + min); } public static void main(String[] args) { Scanner s = new Scanner(System.in); raph G = new raph(s); /*node[] nodes = G.nodes(); for(node n : nodes){ while(n != null){ System.out.print(n.index + " "); n = n.next; } System.out.println(); }*/ for(int i = 0; i < G.V(); i ++){ G.Dijkstra(i); } int[][] D = G.D(); //for(int[] a : D) System.out.println(Arrays.toString(a)); judge(D); } }