门户网站做免费相亲的,十大安卓应用商店排名,wordpress必备优化插件,网站建设 预付款Problem: P2910 [USACO08OPEN] Clear And Present Danger S 文章目录 思路解题方法复杂度Code 思路 这是一个图论问题#xff0c;我们需要找到从一个城市到另一个城市的最短路径。我们可以使用Floyd-Warshall算法来解决这个问题。首先#xff0c;我们需要构建一个距离矩阵我们需要找到从一个城市到另一个城市的最短路径。我们可以使用Floyd-Warshall算法来解决这个问题。首先我们需要构建一个距离矩阵然后使用Floyd-Warshall算法来更新这个矩阵最后我们可以通过这个矩阵来找到最短路径。 解题方法 首先我们需要读取输入数据包括城市的数量n路径的数量m以及每个城市之间的距离。 然后我们需要构建一个距离矩阵初始化所有的距离为无穷大。 接下来我们使用Floyd-Warshall算法来更新距离矩阵。这个算法的基本思想是对于每个城市我们尝试通过这个城市来更新其他城市之间的距离。如果通过这个城市可以使得其他城市之间的距离变短那么我们就更新这个距离。 最后我们可以通过距离矩阵来找到最短路径。我们只需要遍历路径然后累加每两个城市之间的距离就可以得到最短路径的长度。 复杂度
时间复杂度: O ( n 3 ) O(n^3) O(n3)其中n是城市的数量。这是因为Floyd-Warshall算法的时间复杂度是 O ( n 3 ) O(n^3) O(n3)。 空间复杂度: O ( n 2 ) O(n^2) O(n2)其中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;}}
