题目描述

算法1

$O(n^3)$

Java 代码

import java.util.*;
import java.io.*;

public class Main{

    static final int INF = Integer.MAX_VALUE >> 1;
    static int n, m, k;
    static int[][] d;
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        String[] s = cin.readLine().split("\\s+");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);
        d = new int[n+1][n+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; ++j){
                if(i == j){
                    d[i][j] = 0;
                }else{
                    d[i][j] = INF;
                }

            }
        }

        while(m--> 0){
            String[] s1 = cin.readLine().split("\\s+");
            int x = Integer.parseInt(s1[0]);
            int y = Integer.parseInt(s1[1]);
            int z = Integer.parseInt(s1[2]);
            d[x][y] = Math.min(d[x][y], z);
        }
        floyd();
        while(k-- > 0){
            String[] s2 = cin.readLine().split("\\s+");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            if(d[a][b] > INF/2){
                System.out.println("impossible");
            }else{
                System.out.println(d[a][b]);
            }
        }
    }

    static void floyd(){
        for(int k = 1;k <= n; k++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; ++j){
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
}