Floyd
适用于多源最短路径
即多个起点到多个终点的多条最短路径
其对权值正负没有要求，都可以处理
import java.util.*;public class Test{public static void main(String[] args) {Scanner in =new Scanner(System.in);int n=in.nextInt();int m=in.nextInt();int[][]graph=new int [n+1][n+1];for(int i=1;i<=n;i++){Arrays.fill(graph[i],10005);}for(int i=0;i<m;i++){int a=in.nextInt();int b=in.nextInt();int val=in.nextInt();graph[a][b]=val;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){graph[i][j]=Math.min(graph[i][j],graph[i][k]+graph[k][j]);}}}int q=in.nextInt();for(int i=1;i<=q;i++){int start=in.nextInt();int end=in.nextInt();if(graph[start][end]==10005){System.out.println(-1);}else{System.out.println(graph[start][end]);}}}
}
