public class Aha {
static int n;// 输入的城市数
static int m;// 输入的边数
static int[][] path;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = n - 1;
path = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
path[j] = Integer.MAX_VALUE;
}
path = 0;// 控制对角线的值为0,因为城市中自己到自己的距离 就是0 ;
}
for (int i = 1; i <= m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
path[v] = sc.nextInt();
path[v] = path[v];
}
// sop(path);
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (path[j] > path[k] + path[k][j] && path[k] != Integer.MAX_VALUE
&& path[k][j] != Integer.MAX_VALUE)
path[j] = path[k] + path[k][j];
}
}
}
int num = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (path[j] != Integer.MAX_VALUE && path[j] > num)
num = path[j];
}
}
int result = 0;
for (int i = 1; i <= num; i++) {
result += (i + 10);
}
System.out.println(result);
// sop(path);
}
}
深度优先搜索的代码:
[java] view plain copy
在CODE上查看代码片派生到我的代码片
import java.util.Scanner;
public class Main {
static int n;// 输入的城市数
static int m;// 输入的边数
static int[][] path;
static int[] book;
static int dis = Integer.MIN_VALUE, v;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = n - 1;
path = new int[n + 1][n + 1];
book = new int[n + 1];
for (int i = 1; i <= m; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
path[v] = sc.nextInt();
path[v] = path[v];
}
dfs(1, 0);
for (int i = 0; i <= n; i++) {
book = 0;
}