大臣的旅费_Floyd

约定不等于承诺〃 2022-07-12 12:14 123阅读 0赞

package 搜索;  
  
  
import java.util.Scanner;  
  
  
public class 大臣的旅费\_Floyd \{  
public static void main(String\[\] args) \{  
Scanner sc = new Scanner(System.in);  
int n = sc.nextInt();  
int arr\[\]\[\] = new int\[n + 1\]\[n + 1\];  
for (int i = 0; i <= n; i++) \{  
for (int j = 0; j <= n; j++) \{  
arr\[i\]\[j\] = 999999;  
\}  
\}  
for (int i = 0; i < n - 1; i++) \{  
int a = sc.nextInt();  
int b = sc.nextInt();  
int c = sc.nextInt();  
arr\[a\]\[b\] = c;  
arr\[b\]\[a\] = c;  
\}  
for (int k = 1; k <= n; k++) \{  
for (int i = 1; i <= n; i++) \{  
for (int j = 1; j <= n; j++) \{  
if (i != j && arr\[i\]\[j\] > arr\[i\]\[k\] + arr\[k\]\[j\]) \{  
arr\[i\]\[j\] = arr\[i\]\[k\] + arr\[k\]\[j\];  
\}  
  
  
\}  
  
  
\}  
  
  
\}  
int maxDistance = 0;  
for (int i = 1; i <= n; i++) \{  
for (int j = 1; j <= n; j++) \{  
if (arr\[i\]\[j\] == 999999)  
continue;  
if (arr\[i\]\[j\] > maxDistance)  
maxDistance = arr\[i\]\[j\];  
\}  
\}  
  
  
System.out.println(maxDistance \* (21 + maxDistance) / 2);  
\}  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，123人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯历届试题大臣的旅费（两次dfs 之树上求最长路径）

分析：这题刚开始用一个二维数组储存从城市i到城市j，dfs很容易就写出来，但是只得了 75分，原因据说是最后一组数据在10000左右，二维数组明显开不下；好吧，就用vector

﹏ヽ暗。殇╰゛Y/ 2024年02月17日 19:44/ 0 赞/ 5 阅读

相关试题历届试题大臣的旅费(c++)

代码是拷贝其他人的附链接：https://blog.csdn.net/the\_ZED/article/details/104174375?utm\_medium=dis

秒速五厘米/ 2022年12月12日 02:00/ 0 赞/ 142 阅读

相关历届试题大臣的旅费（2次dfs）

问题描述很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案

￡神魔★判官ぃ/ 2022年10月01日 00:57/ 0 赞/ 103 阅读

相关大臣的旅费

问题描述很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方

喜欢ヅ旅行/ 2022年08月21日 02:19/ 0 赞/ 133 阅读

相关 FLOYD

求出图中两顶点间的最短路径，让我们想到的是DIJIKSTRA算法，即单源最短路径的算法。那如果求所有顶点两两之间的最短路径的值，是否只要调用N次DIJIKSTRA了？当

红太狼/ 2022年08月05日 05:08/ 0 赞/ 105 阅读

相关大臣的旅费

很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。为节省经费，T国的大臣们经过思考，制定了一套优

矫情吗；*/ 2022年08月04日 16:51/ 0 赞/ 105 阅读

相关大臣的旅费_Floyd

package 搜索; import java.util.Scanner; public class 大臣的旅费\_Floyd \{ pub

约定不等于承诺〃/ 2022年07月12日 12:14/ 0 赞/ 124 阅读

相关大臣的旅费

package 搜索; import java.io.BufferedInputStream; import java.io.IOExcepti

逃离我推掉我的手/ 2022年07月12日 12:14/ 0 赞/ 115 阅读

相关大臣的旅费2

package 搜索; import java.io.BufferedInputStream; import java.io.IOException;

ゞ浴缸里的玫瑰/ 2022年07月12日 12:13/ 0 赞/ 99 阅读

相关 floyd算法

floyd算法是通过动态规划特别是记住公式，f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = m

喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 363 阅读