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;
				else
					d[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 stub
		for (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;

	}

}