蓝桥杯（蓝桥公园vip试题）

题目描述
小明喜欢观景，于是今天他来到了蓝桥公园。

已知公园有 N 个景点，景点和景点之间一共有 M 条道路。小明有 Q 个观景计划，每个计划包含一个起点 st 和一个终点 ed，表示他想从 st 去到 ed。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？

输入描述
输入第一行包含三个正整数 N,M,Q

第 22 到 M+1 行每行包含三个正整数 u,v,w，表示 u↔v 之间存在一条距离为 w 的路。

第 M+2 到 M+Q−1 行每行包含两个正整数 st,ed，其含义如题所述。

1≤N≤400，1≤M≤N×(N−1)/2，Q≤10^3，1≤u,v,st,ed≤n，1≤w≤10^9

输出描述
输出共 Q 行，对应输入数据中的查询。

若无法从 st 到达 ed 则输出 −1。

输入输出样例
示例 1：
输入

3 3 3
1 2 1
1 3 5
2 3 2
1 2
1 3
2 3

输出
1
3
2

代码分析:

import java.util.Scanner;

public class 蓝桥公园 {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int q = sc.nextInt();
    long max = 0x3f3f3f3f3f3f3f3fL;
    long[][] e = new long[450][450];
    for (int i = 0; i < 450; i++) {
        for (int j = 0; j < 450; j++) {
            e[i][j] = max;
        }
    }
    while (m > 0) {
        int l = sc.nextInt();
        int r = sc.nextInt();
        int v = sc.nextInt();
        e[l][r] = e[r][l] = Math.min(e[l][r], v);// 防止重复
        m--;
    }

// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// System.out.print(ei + " ");
// }
// System.out.println();
// }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (e[j][k] > e[j][i] + e[i][k]) {
                    e[j][k] = e[j][i] + e[i][k];
                }
            }
        }
    }
    while (q > 0) {
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (e[a][b] == max) {
            System.out.println(-1);
        } else if (a == b) {
            System.out.println(0);
        } else
            System.out.println(e[a][b]);
        q--;
    }
}

}