<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                ## 歷屆試題 大臣的旅費 ? 時間限制: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; } } ~~~
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看