Problem: AcWing 854. Floyd求最短路

思路

这是一个经典的图论问题，要求找出所有点对之间的最短路径。我们可以使用Floyd算法来解决这个问题。Floyd算法是一种动态规划的方法，它的基本思想是：对于图中的每一个点，尝试以它作为中间点，更新所有点对之间的最短路径。

解题方法

首先，我们需要初始化一个二维数组d，其中d[i][j]表示点i到点j的最短路径。初始化时，如果i和j是同一个点，那么d[i][j]为0；否则，d[i][j]为无穷大。
然后，我们读入所有的边，并更新对应的d[i][j]。
接下来，我们进行Floyd算法的主要部分。对于每一个点b，我们尝试以它作为中间点，更新所有点对之间的最短路径。具体来说，如果通过b，点i到点j的路径可以变得更短，那么我们就更新d[i][j]。
最后，我们读入所有的查询，输出对应的最短路径。

复杂度

时间复杂度:

Floyd算法的时间复杂度为$O(n^3)$，其中$n$为点的数量。

空间复杂度:

我们需要一个二维数组来存储所有点对之间的最短路径，所以空间复杂度为$O(n^2)$。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int MAXN = 210, INF = 0x3f3f3f3f;static int[][] d = new int[MAXN][MAXN];static int n, m, Q;public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();Q = nextInt();// 初始化for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j)d[i][j] = 0;elsed[i][j] = INF;}}for (int i = 0, x, y, z; i < m; i++) {x = nextInt();y = nextInt();z = nextInt();d[x][y] = Math.min(z, d[x][y]);}floyd();for (int i = 0, a, b; i < Q; i++) {a = nextInt();b = nextInt();out.println(d[a][b] > INF / 2 ? "impossible" : d[a][b]);}out.flush();}private static void floyd() {// TODO Auto-generated method stubfor (int b = 1; b <= n; b++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {d[i][j] = Math.min(d[i][j], d[i][b] + d[b][j]);}}}}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}