854. Floyd求最短路（模板）

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数n，m，k

接下来m行，每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

接下来k行，每行包含两个整数x，y，表示询问点x到点y的最短距离。

输出格式

共k行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出“impossible”。

数据范围

1≤n≤2001≤n≤200,
1≤k≤n21≤k≤n2
1≤m≤200001≤m≤20000,
图中涉及边长绝对值均不超过10000。

输入样例：

输出样例：

impossible

1

代码：

//存在负边，不存在负权回路

import java.util.Scanner;

public class Main{

        static final int N=205, INF=0x3f3f3f3f;

        static int dp[][]=new int[N][N];

        static int n,m,q;

        static void Floyd(){

                for(int k=1;k<=n;k++)

                    for(int i=1;i<=n;i++)

                        for(int j=1;j<=n;j++)

                            dp[i][j]=Math.min(dp[i][j], dp[i][k]+dp[k][j]);

        }

         public static void main(String[] args) {

                 Scanner scan=new Scanner(System.in);

                 n=scan.nextInt();

                 m=scan.nextInt();

                 q=scan.nextInt();

                 for(int i=1;i<=n;i++)

                    for(int j=1;j<=n;j++)

                        if(i==j) dp[i][j]=0;//解决自环

                        else dp[i][j]=INF;

                 while(m-->0){

                         int a=scan.nextInt();

                         int b=scan.nextInt();

                         int w=scan.nextInt();

                         dp[a][b]=Math.min(dp[a][b], w);//解决重边，重边取小的

                 }

                 Floyd();

                 while(q-->0){

                         int a=scan.nextInt();

                         int b=scan.nextInt();

                         if(dp[a][b]>INF/2) System.out.println("impossible");//解决负边

                         else System.out.println(dp[a][b]);

                 }

        }

 }

巴特西