大臣的旅费2

ゞ浴缸里的玫瑰 2022-07-12 12:13 119阅读 0赞

package 搜索;  
  
  
import java.io.BufferedInputStream;  
import java.io.IOException;  
import java.util.Arrays;  
  
  
public class 大臣的旅费2 \{  
static BufferedInputStream bs = new BufferedInputStream(System.in);  
  
static final int INFINITY = 999999;  
  
  
static int readInt() \{  
int num = 0;  
int i = 0;  
try \{  
while (((i = bs.read()) & 48) != 48 || i > 57)  
;  
while ((i & 56) == 48 || (i & 62) == 56) \{  
num = num \* 10 + (i & 15);  
i = bs.read();  
\}  
\} catch (IOException e) \{  
\}  
return num;  
\}  
  
  
static class Edge \{  
public int to;  
public int next;  
public int distance;  
\}  
  
  
static Edge\[\] edge;  
static int\[\] head;  
static int top;  
static boolean\[\] flag;  
static int maxDi;  
static int maxIndex;  
  
  
public static void main(String\[\] args) \{  
int n = readInt();  
init(n);  
for (int i = 0; i < n - 1; i++) \{  
int a = readInt();  
int b = readInt();  
int c = readInt();  
addEdge(a, b, c);  
addEdge(b, a, c);  
\}  
dfs(1, 0);  
dfs(maxIndex, 0);  
System.out.println(maxDi \* (21 + maxDi) / 2);  
\}  
  
  
private static void dfs(int start, int distance) \{  
if (distance > maxDi) \{  
maxDi = distance;  
maxIndex = start;  
\}  
flag\[start\] = true;  
for (int i = head\[start\]; i != -1; i = edge\[i\].next) \{  
int to = edge\[i\].to;  
int dis = edge\[i\].distance;  
if (flag\[to\])  
continue;  
dfs(to, distance + dis);  
\}  
flag\[start\] = false;  
  
  
\}  
  
  
private static void init(int n) \{  
flag = new boolean\[n + 1\];  
edge = new Edge\[(n - 1) \* 2\];  
head = new int\[(n - 1) \* 2\];  
top = 0;  
Arrays.fill(head, -1);  
\}  
  
  
private static void addEdge(int a, int b, int c) \{  
edge\[top\] = new Edge();  
edge\[top\].to = b;  
edge\[top\].next = head\[a\];  
edge\[top\].distance = c;  
head\[a\] = top++;  
  
  
\}  
\}

发表评论取消回复

表情：

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

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

相关阅读

相关历届试题大臣的旅费 dfs

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

偏执的太偏执、/ 2024年02月17日 20:51/ 0 赞/ 9 阅读

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

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

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

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

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

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

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

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

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

相关大臣的旅费

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

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

相关大臣的旅费

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

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

相关大臣的旅费_Floyd

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

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

相关大臣的旅费

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

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

相关大臣的旅费2

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

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

相关 2.2.2 Python异常的处理

对于Python运行当中，遇到异常Python是怎么显示和处理的： \!/usr/bin/env python \coding=utf-8 while True

小灰灰/ 2022年05月28日 11:17/ 0 赞/ 188 阅读