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 stub
		for(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 stub
		for (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;
	}

}