java 代码

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

class Main{

    static int n = 0, m = 0, kc = 0;
    static int N = 210;
    static int INF = 0x3f3f3f3f;
    static int[][] g = new int[N][N];

    static void Flord(){

        for(int k = 1; k <= n; ++k)
            for(int i = 1; i <= n; ++i)
                for(int j = 1; j <= n; ++j)
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);

    }

    public static void main(String[] args)throws Exception{
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        String[] params = buf.readLine().split(" ");
        n = Integer.valueOf(params[0]);
        m = Integer.valueOf(params[1]);
        kc = Integer.valueOf(params[2]);
        for(int i = 1; i<= n; ++i){
            for(int j = 1; j <= n; ++j)
                if(i == j)g[i][j] = 0;
                else g[i][j] = INF;
        }
        for(int i = 1; i<= m; ++i){
            String[] info = buf.readLine().split(" ");
            int a = Integer.valueOf(info[0]);
            int b = Integer.valueOf(info[1]);
            int w = Integer.valueOf(info[2]);
            if(a == b)
                g[a][b] = 0;
            else
                g[a][b] = Math.min(g[a][b], w);
        }
        Flord();
        for(int i = 1; i <= kc; ++i){
            String[] info = buf.readLine().split(" ");
            int a = Integer.valueOf(info[0]);
            int b = Integer.valueOf(info[1]);
            if(g[a][b] > INF / 2)System.out.println("impossible");
            else System.out.println(g[a][b]);
        }
    }
}