nyoj1006（最短路次短路spfa）

布满荆棘的人生 2022-08-27 04:56 219阅读 0赞

## 偷西瓜 ##

时间限制： 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 plain][] [copy][view plain] [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

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. \} 
103.

[view plain]: http://blog.csdn.net/y990041769/article/details/24600127#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/315570
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/315570/fork