xr

public class Main {
	static int n;	// 城市数
	static int node;	// 当前访问节点
	static int[][] map;	// 存放城市图
	static int curWeight = 0;	// 当前路线的权重和，用于比较边权
	static boolean[] visited;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		
		map = new int[n+1][n+1];
		visited = new boolean[n+1];
		for(int i = 0; i<n-1; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int weight = sc.nextInt();
			map[u][v] = map[v][u] = weight;
		}
		// 从第一个节点开始走
		dfs(1,0);
		curWeight = 0;
		dfs(node,0);
		int res = getCost(curWeight);
		System.out.print(res);
	}
	/**
	 * 
	 * @param start
	 * @param weight	// 权重和
	 */
	private static void dfs(int start, int weight) {
		// TODO Auto-generated method stub
		if(weight>curWeight) {
			curWeight = weight;
			node = start;	// 保存当前权重和最多的节点
		}
		for(int i = 0; i<n; i++) {
			if(!visited[i] && map[start][i]!=0) {
				visited[start]= true;
				visited[i] = true;
				dfs(i,weight+map[start][i]);
				visited[start] = false;
				visited[i] = false;
			}
		}
	}
	//根据千米获得需要的费用
    public static int getCost(int k) {
        int sum=0;
        for (int i = 1; i <=k; i++) {
            sum+=(i+10);
        }
        return sum;
    }
}
```

## 邻接表
考虑到本题中涉及的边少，所以可以改用邻接表，这样就不会有内存超限的问题
```
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Vector;

public class 第四届2013_大臣的旅费_邻接表 {
	static int n;	// 城市数
	static List<Node>[] list;	// 构建邻接表
	static boolean visited;
	static int curWeight,node;	// 当前权重和，当前节点
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		// 构建邻接表
		list = new List[n+1];
		for(int i = 1; i<=n; i++) {
			list[i] = new ArrayList<Node>();
		}
		for(int i = 0; i<n-1; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int weight = sc.nextInt();
			list[u].add(new Node(v,weight));
			list[v].add(new Node(u,weight));
		}
		dfs(1,1,0);
		dfs(node,node,0);
		System.out.print(getCost(curWeight));
	}
	/**
	 * 
	 * @param from	上一个点
	 * @param cur	当前节点
	 * @param weight	权重和
	 */
	private static void dfs(int from, int cur, int weight) {
		// TODO Auto-generated method stub
		if(visited&&weight>curWeight) {
			curWeight=weight;	// 记录下当前权重和
			node=cur;	// 记录下当前访问的节点
		}
		// 找出邻接表中当前的链表
		List<Node> neighboors = list[cur];
		// 遍历邻接表中当前的链表中的节点
		for(int i =0; i<neighboors.size(); i++) {
			Node neighboor = neighboors.get(i);
			if(neighboor.v==from) continue;
			visited = true;
			dfs(cur, neighboor.v, weight+neighboor.dis);
			visited = false;
		}
		
	}
	//根据千米获得需要的费用
    public static int getCost(int k) {
        int sum=0;
        for (int i = 1; i <=k; i++) {
            sum+=(i+10);
        }
        return sum;
    }
    
	public static class Node{
		int v;
		int dis;
		public Node(int v,int dis) {
			this.v=v;
			this.dis=dis;
		}
	}
}

```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

xr

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

母牛的故事（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

大臣的旅费-两次dfs+邻接矩阵或邻接表

评论区

精彩推荐

聪明的美食家（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言训练-求素数问题（C语言代码）

【蟠桃记】（C语言代码）

简单的a+b （C++语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

xr

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （Java代码）

母牛的故事 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

大臣的旅费-两次dfs+邻接矩阵或邻接表

评论区

精彩推荐

聪明的美食家 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

简单的a+b （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

C语言训练-求素数问题 （C语言代码）

【蟠桃记】 （C语言代码）

简单的a+b （C++语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

母牛的故事（C语言代码）

　　评论区

聪明的美食家（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言训练-求素数问题（C语言代码）

【蟠桃记】（C语言代码）