這道題我也不會寫，然后參考了這篇---->

https://blog.csdn.net/Look_star/article/details/88032821

只是我覺得他的描述還不夠清晰，所以把自己理解的思路完善一下。

注：

不懂這個：

求一棵樹之間兩點最長的距離，即樹的直徑。

所以又搜了資料：

出自：https://www.cnblogs.com/tonghao/p/4740425.html

要用兩次DFS求最長的距離。

而最遠(yuǎn)的點G-D，他們之間的距離即整棵樹距離最長。

這里默認(rèn)他們的權(quán)值為1，只是為了說明原理，具體搜索要根據(jù)路徑的權(quán)值來定。

先給出所有的代碼，然后對代碼各部分進行詳細(xì)解釋。

1 importjava.util.ArrayList;2 importjava.util.Arrays;3 importjava.util.Scanner;4

5 //動態(tài)鏈表

6 classVertex{7 ArrayList V=newArrayList();8 }9 classEdge{10 ArrayList E=newArrayList();11 }12

13 public classMain {14 final static int INF=0X3f3f3f3f;//10^9一般數(shù)都達不到這個，所以用它作為最大值

15 final static int maxn=100000;16 static Vertex[] v=new Vertex[maxn+5];//V[i]存儲與i相鄰接的節(jié)點

17 static Edge[] e=new Edge[maxn+5];//e[i]存儲與i鄰接的邊的距離

18 static boolean vis[]=new boolean[maxn+5];//防止重復(fù)訪問

19 static int dis[]=new int[maxn+5];//存儲原始結(jié)點到各結(jié)點的dfs距離

20

21 static void init(int n){//初始化

22 for(int i=0;i

24 e[i]=newEdge();25 }26 }27

28 static void dfs(inta){29 int len=v[a].V.size();//與a相鄰接的城市有幾個

30 vis[a]=true;//a城市已經(jīng)訪問

31 for(int i=0;i

32 int j=v[a].V.get(i);//依次獲取a鄰接的幾個城市

33 if(!vis[j]&&e[a].E.get(i)!=INF){34 vis[j]=true;35 dis[j]=dis[a]+e[a].E.get(i);36 dfs(j);37 vis[j]=false;//回溯

38 }39 }40 }41

42 public static voidmain(String[] args) {43 Scanner sc=newScanner(System.in);44 int n=sc.nextInt();45

46 init(n);47

48 for(int i=0;i

53 e[a].E.add(c);//用e記錄對應(yīng)的a-b的距離

54 v[b].V.add(a);//反之b可以到a

55 e[b].E.add(c);//用e記錄對應(yīng)的b-a的距離

56 }57

58 //此類包含用來操作數(shù)組(比如排序和搜索)的各種方法59 //將制定的false,INF分配給對應(yīng)數(shù)組中的每個元素，相當(dāng)于for初始操作的簡化

60 Arrays.fill(vis,false);61 Arrays.fill(dis,INF);62

63 dis[0]=0;64 dfs(0);//第一次遍歷 求得某個城市到最遠(yuǎn)的城市的最大距離是多少，并用dis[]來記錄 比如sid[1]=67;

65 long max=-1;66 int temp=-1;67 for(int i=0;imax){69 max=dis[i];70 temp=i;71 }72 }73

74 Arrays.fill(vis, false);75 Arrays.fill(dis, INF);76

77 dis[temp]=0;78 dfs(temp);//第二次遍歷 求b與？距離最遠(yuǎn)

79 long ans=-1;//防止越界

80 for(int i=0;ians){82 ans=dis[i];83 temp=i;84 }85 }86 ans=ans*(ans+21)/2;87 System.out.println(ans);88 sc.close();89

90 }91

92 }

自定義兩個類，分別構(gòu)造了動態(tài)鏈表。

INF=0X3f3f3f3f可自行百度，簡潔意思就是0X3f3f3f3f即十進制的 10的9次方，表示一個超大的數(shù)，一般情況都達不到。此處用作后面作為一個標(biāo)志。

maxn作用可能是因為在藍橋杯提交檢測時最后輸入的n是10000；所以在初始定義的時候就先創(chuàng)建一個比10000大的范圍，所以 后面用了 maxn+5

init(n)就是確定具體的動態(tài)鏈表多長

看main方法中：

DFS深度優(yōu)先搜索：

在之前，先把數(shù)據(jù)準(zhǔn)備好，

執(zhí)行過程——> 可能有些亂。。但花了很久時間。

第一次dfs結(jié)束后，dis[ ]存儲了0到各城市的距離，在之后的操作中就是得到最遠(yuǎn)距離max，且用temp記錄下與0最遠(yuǎn)的城市，也就是城市4，下標(biāo)為3

第二次遍歷就是從3開始了。這次要找到距離3最遠(yuǎn)的城市。步驟原理同上，

這是第二次DFS結(jié)束，可以看出最遠(yuǎn)的應(yīng)該是dis[4] 距離為9

然后進行最后的計算就可以得出所花費的錢了。

好像代碼里的注解會有些錯誤，因為代碼里的注釋不是最后的理解，有錯好像沒更改過來？

有點奇怪的是兩次提交一個正確一個錯誤，中間好像沒怎么修改啊，出現(xiàn)兩個結(jié)果我還是有些一頭霧水。

這個代碼是之前的，如果運行錯誤，可找原文的代碼，配上我寫的注釋一起看。

總結(jié)

以上是生活随笔為你收集整理的java 大臣的旅费_PREV-9-蓝桥杯-历届试题-大臣的旅费-java的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。