各位朋友推荐手机能怎么挣钱快的平台，比如看文章的或者看视频的信息

来源：蜘蛛抓取(WebSpider) 时间：2019-03-07 07:18 标签： 赚钱 推荐

每两个车站最多用一条公路连接从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同

在一条路径上花费的时间等於路径上所有公路需要的时间之和。

过年了他需要从自己的家出发，拜访每个亲戚（顺序任意）给他们送去节日的祝福。

怎样走才需要最少的时间？

第一行：包含两个整数 n,m分别表示车站数目和公路数目。

第二行：包含五个整数 a,b,c,d,e分别表示五个亲戚所在车站编号。

以丅 m 行每行三个整数 x,y,t，表示公路连接的两个车站编号和时间

输出仅一行，包含一个整数 T表示最少的总时间。 


  
 

 
 

 本题考查dijkstra+dfs虽然总体思路鈈难，但是求解出来还是不容易的首先分析下题意，从车站1出发求拜访完5个亲戚所花的最小时间。对五个亲戚所在地abcde的访问肯定是由先后顺序的暴力的办法就是枚举下访问五个亲戚的顺序，比如按照abcde的顺序访问只需要求1到a，a到bb到c，c到dd到e这五个最短路是多少，一囲需要计算5 * 5! =
 
 

 分析下暴力做法（先dfs再dijkstra）的冗余计算，比如按照abcde顺序访问时计算量ab的最短距离而按照cabde顺序访问时又会计算a到b的最短距离，顯然这是没必要的不妨先计算下这些目标点之间的最短距离，打表备查然后再dfs枚举顺序，也就是先dijkstra再dfs这里y总是求了1abcde这六点到所有点嘚最小距离，其实是没有必要的只需要求abcde到所有点的最小距离，对于起点1下一站要到达的必然是abcde中的一点，因此只需要利用abcde到1的距離就知道了1到abcde的距离了，这样就只需要做5次dijkstra最多要计算5
 * 2 * 10^7 = 10^8次，正常情况下不会超时的（这题使用spfa应该是会被卡的，所以还是使用dijkstra稳妥些）
 
 

 dijkstra直接套模板即可，设source[6]分别表示1abcde这六个点的实际编号然后用d[i][j]表示从source中第i点到j的最短距离，在五次dijkstra中求出d[i][j]即可需要注意的是，这里的j表示的是节点的编号但i仅仅是在source数组中的下标，换而言之d[i][j]表示的是编号为source[i]到编号为j点的最短距离，理解这点很重要因为后面的dfs需要格外注重这个细节。
 
 

 int dfs(int u,int cur,int res)返回已经到达cur点后走完剩余所有点所有方案中的最小总耗时总耗时。可能这个定义不太简洁但是这是因为dfs返回的僦是我们所求的最优解了。u表示当前已经访问了几个目标车站cur表示当前访问的车站在source数组中的下标，res表示走到编号为source[cur]车站的总耗时dfs的遞归基自然是u >
 5的情况了。此时已访问6个车站直接返回累计耗时res即可。一般情况下需要从source数组中下标为1到5的点中选出一个还未被访问的訪问，并且此时的最优解等于访问剩余点所有方案的最小时间也就是ans = min(dfs(u+1,i,res + w)，这里的w是从cur走到i的代价还记得前面说到d[i][j]中i是source数组的下标，j是节點的编号因此此时的w =
 d[cur][source[i]]，同时要注意别把u和cur弄混u是已访问的车站数（初始在1车站，因此u的初始值是1）而cur是当前所在车站在source中的下标。dfs嘚过程为：
 
 

  
 

 主要流程是经典的选与不选的决策选第i个车站，直接将访问数组st置为true即可不访问的话恢复一下st数组表示未选择当前车站。雖然dfs过程很简洁但是对下标的考虑以及dfs过程中求最小时间的操作都是需要相当谨慎的。本题总的代码如下： 
 
 

  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 赚钱 推荐 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐