首页 > 代码库 > nyoj1006（最短路次短路spfa）

nyoj1006（最短路次短路spfa）

2024-07-04 00:23:25   227人阅读

偷西瓜

时间限制：1000 ms  |  内存限制：65535 KB
难度：4
描述

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


代码：

[cpp] view plaincopyprint?在CODE上查看代码片派生到我的代码片
  1. #include <cstdio>  
  2. #include <vector>  
  3. #include <iostream>  
  4. #include <stack>  
  5. #include <cstdio>  
  6. #include <string>  
  7. #include <cstring>  
  8. #include <cmath>  
  9. #include <algorithm>  
  10. #include <queue>  
  11. using namespace std;  
  12. const int inf = 0x3f3f3f3f;  
  13. const int N = 300;  
  14. struct Point  
  15. {  
  16.     int x,y;  
  17.     int r;  
  18.     int num;  
  19. };  
  20. Point a[N];  
  21. struct Node  
  22. {  
  23.     int v,len;  
  24. };  
  25. vector<Node> map[N];  
  26. int n,m;  
  27. void spfa(int s,int dis[])  
  28. {  
  29.     int i,pre[N];  
  30.     bool used[N];  
  31.     queue<int> q;  
  32.     memset(used,0,sizeof(used));  
  33.     memset(pre,-1,sizeof(pre));  
  34.     for(i=0; i<N; i++)  
  35.         dis[i]=inf;  
  36.     dis[s]=0;  
  37.     used[s]=true;  
  38.     q.push(s);  
  39.     while(!q.empty())  
  40.     {  
  41.         int u=q.front();  
  42.         q.pop();  
  43.         used[u]=false;  
  44.         for(i=0; i<map[u].size(); i++)  
  45.         {  
  46.             Node p=map[u][i];  
  47.             if(dis[p.v]>dis[u]+p.len)  
  48.             {  
  49.                 dis[p.v]=dis[u]+p.len;  
  50.                 pre[p.v]=u;  
  51.                 if(!used[p.v])  
  52.                 {  
  53.                     used[p.v]=true;  
  54.                     q.push(p.v);  
  55.                 }  
  56.             }  
  57.         }  
  58.     }  
  59.     for(int i=n;pre[i]!=-1;i=pre[i])  
  60.     {  
  61. //        printf("%d ",pre[i]);  
  62.         for(int j=0;j<map[i].size();j++)  
  63.         {  
  64.             if(map[i][j].v==pre[i])  
  65.                 map[i].erase(map[i].begin()+j);  
  66.         }  
  67.         for(int j=0;j<map[pre[i]].size();j++)  
  68.         {  
  69.             if(map[pre[i]][j].v==i)  
  70.                 map[pre[i]].erase(map[pre[i]].begin()+j);  
  71.         }  
  72.     }  
  73. }  
  74. int main()  
  75. {  
  76.     int dis1[N];  
  77.     while(~scanf("%d%d",&n,&m))  
  78.     {  
  79.         for(int i=0;i<=n;i++)  
  80.             map[i].clear();  
  81.         for(int i=0;i<m;i++)  
  82.         {  
  83.             int x,y,z;  
  84.             scanf("%d%d%d",&x,&y,&z);  
  85.             Node tmp;  
  86.             tmp.v=y,tmp.len=z;  
  87.             map[x].push_back(tmp);  
  88.             tmp.v=x;  
  89.             map[y].push_back(tmp);  
  90.         }  
  91.         int ans=0;  
  92.         spfa(1,dis1);  
  93.         ans+=dis1[n];  
  94.         spfa(1,dis1);  
  95.         ans+=dis1[n];  
  96.         if(ans>=inf)  
  97.             printf("eating\n");  
  98.         else  
  99.             printf("%d\n",ans);  
  100.     }  
  101.     return 0;  
  102. }  


联系
我们