【最短路】Acwing1128信使：floyd最短路

 

import java.io.*;
import java.util.*;
class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final int N=1000;
    static final int INF=(int)1e8;
    static int[][] dist=new int[N][N];
    static int n,m;
    public static void main(String[]args)throws IOException{
        String[] s=br.readLine().split(" ");
        n=Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);
        for(int i=1;i<=n;i++)
        Arrays.fill(dist[i],INF);
        for(int i=1;i<=n;i++){
            dist[i][i]=0;
        }
   
        for(int i=0;i<m;i++){
            s=br.readLine().split(" ");
            int a=Integer.parseInt(s[0]);
            int b=Integer.parseInt(s[1]);
            int c=Integer.parseInt(s[2]);
            dist[a][b]=dist[b][a]=Math.min(dist[a][b],c);
      
        }

        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
                }
            }
        }
        
        int res=0;
        for(int i=1;i<=n;i++){
            res=Math.max(dist[1][i],res);
   
        }
        if(res>INF/2)System.out.println(-1);
        else System.out.println(res);
    }
    
}