## 歷屆試題 大臣的旅費 ? 時間限制：1.0s ? 內存限制：256.0MB ????? 問題描述 很久以前，T王國空前繁榮。為了更好地管理國家，王國修建了大量的快速路，用于連接首都和王國內的各大城市。 為節省經費，T國的大臣們經過思考，制定了一套優秀的修建方案，使得任何一個大城市都能從首都直接或者通過其他大城市間接到達。同時，如果不重復經過大城市，從首都到達每個大城市的方案都是唯一的。 J是T國重要大臣，他巡查于各大城市之間，體察民情。所以，從一個城市馬不停蹄地到另一個城市成了J最常做的事情。他有一個錢袋，用于存放往來城市間的路費。 聰明的J發現，如果不在某個城市停下來修整，在連續行進過程中，他所花的路費與他已走過的距離有關，在走第x千米到第x+1千米這一千米中（x是整數），他花費的路費是x+10這么多。也就是說走1千米花費11，走2千米要花費23。 J大臣想知道：他從某一個城市出發，中間不休息，到達另一個城市，所有可能花費的路費中最多是多少呢？ 輸入格式 輸入的第一行包含一個整數n，表示包括首都在內的T王國的城市數 城市從1開始依次編號，1號城市為首都。 接下來n-1行，描述T國的高速路（T國的高速路一定是n-1條） 每行三個整數Pi, Qi, Di，表示城市Pi和城市Qi之間有一條高速路，長度為Di千米。 輸出格式 輸出一個整數，表示大臣J最多花費的路費是多少。 樣例輸入1 5 1 2 2 1 3 1 2 4 5 2 5 4 樣例輸出1 135 輸出格式 大臣J從城市4到城市5要花費135的路費。 這道題，如果不看提示，感覺像是圖論題（有點忒明顯了）， 但是，提示說是 深度優先遍歷，恩，于是DFS做了。 打表存某點到某點的距離，不能到達則為-1. 這樣DFS做 75分。。 YM用Floyed做也是75分。。。 最后一組數據據說是10000左右， DFS打表是存不下這么大數組，超空間了。 等回頭用別的方法試試，之前測試過一個JAVA程序，是可以過的，測試數據應該就沒有問題了。 我的DFS（75分） ~~~ /******************** ********************* * Author:Tree * *From :http://blog.csdn.net/lttree * * Title : 大臣的旅費 * *Source: 藍橋杯 歷屆試題 * * Hint : 深度優先遍歷 * ********************* ********************/ #include <iostream> #include <string.h> using namespace std; int n,val,Map[1001][1001]; bool vis[1001][1001]; void dfs(int i,int v) { int j; for( j=1;j<=n;++j ) { if( Map[i][j]==-1 || vis[i][j] ) continue; vis[i][j]=vis[j][i]=1; dfs( j,v+Map[i][j] ); vis[i][j]=vis[j][i]=0; } val= v>val?v:val; } int find_max( void ) { int i,Max; Max=-1; for(i=1;i<=n;++i) { memset(vis,0,sizeof(vis)); val=-1; dfs(i,0); Max= val>Max?val:Max; } return Max; } int main() { int i,p,q,d,num,sum; while( cin>>n ) { memset(Map,-1,sizeof(Map)); for(i=1;i<n;++i) { cin>>p>>q>>d; Map[p][q]=d; Map[q][p]=d; } num=find_max(); if( num&1 ) sum= (num+1)*(num/2)+(num+1)/2; else sum=(num*num+num)/2; cout<<sum+num*10<<endl; } return 0; } ~~~ 那個100分能過的 JAVA代碼（非本人所寫） ~~~ import java.util.*; public class Main { public static void main(String args[]){ Scanner scan=new Scanner (System.in); int n=scan.nextInt(); QiDian[] QiDians=new QiDian[n]; for(int i=0;i<n;i++){ QiDians[i]=new QiDian(i,new ArrayList<ZhongDian>()); } int tem1=0; int tem2=0; int quanzhong=0; for(int i=0;i<n-1;i++){ tem1=scan.nextInt(); tem2=scan.nextInt(); quanzhong=scan.nextInt(); QiDians[tem1-1].list.add(new ZhongDian(quanzhong,QiDians[tem2-1])); QiDians[tem2-1].list.add(new ZhongDian(quanzhong,QiDians[tem1-1])); } int[] data=search(QiDians[0],null); int[] data2=search(QiDians[data[1]],null); int sum=0; for(int i=1;i<=data2[0];i++){ sum+=i+10; } System.out.println(sum); } public static int[] search(QiDian q,QiDian p){ int[] data=new int[]{0,q.index}; for(int i=0;i<q.list.size();i++){ if(q.list.get(i).qidian.equals(p)==false){ int [] data2=search(q.list.get(i).qidian,q); int tem=q.list.get(i).quanzhong+data2[0]; if(tem>data[0]){ data[0]=tem; data[1]=data2[1]; } } } return data; } } class QiDian{ int index; ArrayList<ZhongDian> list=new ArrayList<ZhongDian>(); public QiDian(int index, ArrayList<ZhongDian> list) { super(); this.index = index; this.list = list; } } class ZhongDian{ int quanzhong; QiDian qidian; public ZhongDian(int quanzhong, QiDian qidian) { super(); this.quanzhong = quanzhong; this.qidian = qidian; } } ~~~