历届试题大臣的旅费-白红宇

历届试题大臣的旅费

阅读量：5076 次

发布时间：2019-06-12

本文共 1808 字，大约阅读时间需要 6 分钟。

历届试题大臣的旅费

时间限制：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

样例输出1

135

输出格式

大臣J从城市4到城市5要花费135的路费。

解题思路：本来我是用的N个bfs，一直卡在第四组数据上，一直超时。从网上看到第四组测试数据是10000，10000个bfs肯定就超时了。

然后从网上看到别人的代码只执行两遍函数就够了，第一遍用于寻找最长路的一个端点，第二次再从这个点出发计算最长路。

刚开始我很不理解，然后经过重新思考图之后，发现图有个特点，因为题目中说只有N-1条边嘛，并且不会重复经过某个城市，说明这个图是没有环的，应该是一个无向无环图。那么（无论从哪一个点出发），假设从1出发，所找到的最长的一条路（从1出发的的最长路），这条路的另一个端点一定是真正最长路的一个端点！

然后两个bfs就可以了。。。

另外bfs，dfs都可以通过这个题。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define FOR(i,x,n) for(long i=x;i
              
                graph[10005];int maxx=0;int costt[10005];int ma[10005]={ 0};node2 date[10005];int point=0;int cmp(node2 a,node2 b){ return a.c>b.c;}void setCost(){ costt[1]=11; FOR(i,2,20000){ costt[i]=costt[i-1]+i+10; }}void bfs(int s){ fill(ma,ma+10000,0); queue
               
                 que; node t={s,0}; que.push(t); ma[t.point]++; while(!que.empty()){ node now=que.front();que.pop(); vector
                
                 ::iterator it; for(it=graph[now.point].begin();it!=graph[now.point].end();it++){ node next=now; node tt=*it; next.cost+=tt.cost; next.point=tt.point; if(ma[next.point]!=0){ continue; } ma[next.point]++; que.push(next); if(maxx

转载于:https://www.cnblogs.com/TWS-YIFEI/p/6492183.html

你可能感兴趣的文章