题目链接：
题目描述
小明喜欢观景，于是今天他来到了蓝桥公园。
已知公园有 N 个景点，景点和景点之间一共有 M条道路。小明有 Q个观景计划，每个计划包含一个起点 st和一个终点 ed，表示他想从 stst 去到 ed。但是小明的体力有限，对于每个计划他想走最少的路完成，你可以帮帮他吗？
输入描述
输入第一行包含三个正整数 N,M,Q
第 2 到 M + 1 行每行包含三个正整数 u,v,w表示 vu↔v 之间存在一条距离为 w 的路。
第 M+2 到 M + Q-1 行每行包含两个正整数 st,ed，其含义如题所述。
输出描述
输出共 Q 行，对应输入数据中的查询。
若无法从 st 到达 eded 则输出 −1。
输入输出样例
示例 1
输入
3 3 3 1 2 1 1 3 5 2 3 2 1 2 1 3 2 3
输出
1 3 2
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 3s | 256M |
| Python3 | 50s | 256M |
JAVA：
import java.util.Arrays; import java.util.Scanner; public class 蓝桥公园 { private static final long INF = 0x3f3f3f3f3f3f3f3fL; private static final int N = 405; private static long[][] dp = new long[N][N]; private static int n, m, q; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); q = scanner.nextInt(); for (long[] row : dp) { Arrays.fill(row, INF); } for (int i = 0; i < m; i++) { int u = scanner.nextInt(); int v = scanner.nextInt(); long w = scanner.nextLong(); dp[u][v] = dp[v][u] = Math.min(dp[u][v], w); } floyd(); while (q-- > 0) { int s = scanner.nextInt(); int t = scanner.nextInt(); if (dp[s][t] == INF) { System.out.println(-1); } else if (s == t) { System.out.println(0); } else { System.out.println(dp[s][t]); } } } private 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]); } } } } }
C/C++：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 405; const ll INF = 0x3f3f3f3f3f3f3f3fLL; ll dis[N][N]; int n, m, q; int main() { cin >> n >> m >> q; memset(dis, 0x3f, sizeof dis); for (int i = 1; i <= n; i++) dis[i][i] = 0; for (int i = 1; i <= m; i++) { ll u, v, w; cin >> u >> v >> w; dis[u][v] = dis[v][u] = min(dis[u][v], w); // 防止出现重边 } // floyd for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); // 输出 int s, t; for (int i = 0; i < q; i++) { cin >> s >> t; ll ans = dis[s][t] == INF ? -1 : dis[s][t]; cout << ans << endl; } return 0; }
