P2910 [USACO08OPEN] Clear And Present Danger S

Problem: P2910 [USACO08OPEN] Clear And Present Danger S

思路

这是一个图论问题，我们需要找到从一个城市到另一个城市的最短路径。我们可以使用Floyd-Warshall算法来解决这个问题。首先，我们需要构建一个距离矩阵，然后使用Floyd-Warshall算法来更新这个矩阵，最后我们可以通过这个矩阵来找到最短路径。

解题方法

首先，我们需要读取输入数据，包括城市的数量n，路径的数量m，以及每个城市之间的距离。
然后，我们需要构建一个距离矩阵，初始化所有的距离为无穷大。
接下来，我们使用Floyd-Warshall算法来更新距离矩阵。这个算法的基本思想是，对于每个城市，我们尝试通过这个城市来更新其他城市之间的距离。如果通过这个城市可以使得其他城市之间的距离变短，那么我们就更新这个距离。
最后，我们可以通过距离矩阵来找到最短路径。我们只需要遍历路径，然后累加每两个城市之间的距离，就可以得到最短路径的长度。

复杂度

时间复杂度:

$O(n^3)$，其中n是城市的数量。这是因为Floyd-Warshall算法的时间复杂度是$O(n^3)$。

空间复杂度:

$O(n^2)$，其中n是城市的数量。这是因为我们需要一个n*n的矩阵来存储城市之间的距离。

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 = 110;static int MAXM = 100010;static int[] path = new int[MAXM];static int[][] distance = new int[MAXN][MAXN];static int n, m, ans;public static void main(String[] args) throws IOException {n = nextInt();m = nextInt();for (int i = 0; i < m; i++) {path[i] = nextInt() - 1;}build();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {distance[i][j] = nextInt();}}floyd();ans = 0;for (int i = 1; i < m; i++) {ans += distance[path[i - 1]][path[i]];}out.println(ans);out.flush();}private static void floyd() {// TODO Auto-generated method stubfor(int bridge = 0; bridge < n; bridge++) {for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {if(distance[i][bridge] != Integer.MAX_VALUE && distance[bridge][j] != Integer.MAX_VALUE&& distance[i][j] > distance[i][bridge] + distance[bridge][j]) {distance[i][j] = distance[i][bridge] + distance[bridge][j];}}}}}private static void build() {// TODO Auto-generated method stubfor (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {distance[i][j] = Integer.MAX_VALUE;}}}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}