nyoj 1006（最短路次短路）

偷西瓜

描述

对于农村的孩子来说最大的乐趣，莫过于和小伙伴们一块下地偷西瓜了，虽然孩子们条件不是很好，但是往往他们很聪明，他们总在计算着到达瓜田的距离，以及逃跑的路线，他们总是以最短的距离冲到瓜田里面，然后以最短的距离回到出发的地方，不过瓜田的大人们已经在他们来的路上等待他们。于是聪明的小伙伴们便不走过的路，即每条路只走一遍,如果小伙伴们回不到出发的地方，他们就说“eating”，

我们假设 有 n (n<=100)个 村庄 m条路(m<=1000)小伙伴们总是从1号村庄出发，而瓜田总是在n号村庄.如果小伙伴们到达不了n号村庄，或者回不到1号村庄请输出"eating";

输入

多组数据
第一行一个整数 n
第二行 一个整数 m
随后的m行 有 三个数u,v,w 表示u 到 v村庄的距离为w(w<=1000);

输出

求小伙伴们从1号村庄出发，到 n号村庄，再回到1号村庄所用的最短距离，如果不能回到1号村庄请输出“eating”.

样例输入

2
1
1 2 999
3
3
1 3 10
2 1 20
3 2 50

样例输出

eating
80

上传者

分析：求一个最短路和一个次短路的和。

那么我们用spfa求一次从1到n的最短路，然后顺便记录路径，然后求完之后把走过的路径删去。然后在求一次1到n的最短路。

spfa讲解：http://blog.csdn.net/y990041769/article/details/18367665

代码：

#include 
      
       
#include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 using namespace std; const int inf = 0x3f3f3f3f; const int N = 300; struct Point { int x,y; int r; int num; }; Point a[N]; struct Node { int v,len; }; vector
                
                  map[N]; int n,m; void spfa(int s,int dis[]) { int i,pre[N]; bool used[N]; queue
                 
                   q; memset(used,0,sizeof(used)); memset(pre,-1,sizeof(pre)); for(i=0; i
                  
                   dis[u]+p.len) { dis[p.v]=dis[u]+p.len; pre[p.v]=u; if(!used[p.v]) { used[p.v]=true; q.push(p.v); } } } } for(int i=n;pre[i]!=-1;i=pre[i]) { // printf("%d ",pre[i]); for(int j=0;j
                   
                    =inf) printf("eating\n"); else printf("%d\n",ans); } return 0; }
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

分享到： 更多

<script type="text/java script" id="bdshare_js" data="type=tools&uid=12732"> <script type="text/java script" id="bdshell_js"> <script type="text/java script"> var bds_config = {'snsKey':{'tsina':'2386826374','tqq':'5e544a8fdea646c5a5f3967871346eb8'}}; document.getElementById("bdshell_js").src = "http://bdimg.share.baidu.com/static/js/shell_v2.js cdnversion=" + Math.ceil(new Date()/3600000)