HDU 2544 最短路(各种最短路算法的实现)

谁借莪１个温暖的怀抱￠ 2022-08-09 13:45 439阅读 0赞

**链接：**

[http://acm.hdu.edu.cn/showproblem.php?pid=2544][http_acm.hdu.edu.cn_showproblem.php_pid_2544]

**题目：**

**Problem Description**

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

**Input**

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。  
输入保证至少存在1条商店到赛场的路线。

**Output**

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

**Sample Input**

2 1

1 2 3

3 3

1 2 5

2 3 5

3 1 2

0 0

**Sample Output**

**Source**

[UESTC 6th Programming Contest Online][]

基础最短路，不解释，其实是专门用来验证各种最短路模板的。

在网上搜索的某神的博客，这些模板题其实没什么来讲的，自己再敲一遍和这也差不太远，图论的话多看书！

附原文链接：*** [http://blog.csdn.net/shuangde800][http_blog.csdn.net_shuangde800] ***

**1.    Dijkstra  普通版**

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include<cstdio>  
2.  \#include<cstring>  
3.  **const** **int** N=105, INF=9999999;  
4.  **int** d\[N\], w\[N\]\[N\],vis\[N\],n,m;  
5.      
6.  **void** Dijkstra(**int** src)\{  
7.      **for**(**int** i=1; i<=n; ++i)  
8.          d\[i\] = INF;  
9.      d\[src\] = 0;   
10.     memset(vis, 0, **sizeof**(vis));  
11.     **for**(**int** i=1; i<=n; ++i)\{  
12.         **int** u=-1;  
13.         **for**(**int** j=1; j<=n; ++j)**if**(!vis\[j\])\{  
14.             **if**(u==-1 || d\[j\]<d\[u\]) u=j;  
15.         \}  
16.         vis\[u\] = 1;  
17.         **for**(**int** j=1; j<=n; ++j)**if**(!vis\[j\])\{  
18.             **int** tmp = d\[u\] + w\[u\]\[j\];  
19.             **if**(tmp<d\[j\]) d\[j\] = tmp;  
20.         \}  
21.     \}  
22. \}  
23. **int** main()\{  
24.     **int** a,b,c;  
25.     **while**(~scanf("%d%d",&n,&m)&&n+m)\{  
26.         **for**(**int** i=1; i<=n; ++i)\{  
27.             w\[i\]\[i\] = INF;  
28.             **for**(**int** j=i+1; j<=n; ++j)  
29.                 w\[i\]\[j\] = w\[j\]\[i\] = INF;  
30.         \}  
31.         **for**(**int** i=0; i<m; ++i)\{  
32.             scanf("%d%d%d",&a,&b,&c);  
33.             w\[a\]\[b\] = w\[b\]\[a\] = c;  
34.         \}  
35.         Dijkstra(1);  
36.         printf("%d\\n", d\[n\]);  
37.     \}  
38.     **return** 0;  
39. \}

**2. Dijkstra+邻接表(用数组实现)+优先队列优化**

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include<cstdio>  
2.  \#include<cstring>  
3.  \#include<utility>  
4.  \#include<queue>  
5.  **using** **namespace** std;  
6.      
7.  **const** **int** N=20005;  
8.  **const** **int** INF=9999999;  
9.      
10. **typedef** pair<**int**,**int**>pii;  
11. priority\_queue<pii, vector<pii>, greater<pii> >q;  
12.     
13. **int** d\[N\], first\[N\], u\[N\], v\[N\], w\[N\], next\[N\],n,m;  
14. **bool** vis\[N\];  
15.     
16.     
17. // 无向图的输入，注意每输入的一条边要看作是两条边  
18. **void** read\_graph()\{  
19.     memset(first, -1, **sizeof**(first)); //初始化表头  
20.     **for**(**int** e=1; e<=m; ++e)\{  
21.         scanf("%d%d%d",&u\[e\], &v\[e\], &w\[e\]);  
22.         u\[e+m\] = v\[e\]; v\[e+m\] = u\[e\]; w\[e+m\] = w\[e\];  // 增加一条它的反向边  
23.             
24.         next\[e\] = first\[u\[e\]\];  // 插入链表  
25.         first\[u\[e\]\] = e;  
26.     
27.         next\[e+m\] =first\[u\[e+m\]\]; // 反向边插入链表  
28.         first\[u\[e+m\]\] = e+m;  
29.     \}  
30. \}  
31.     
32. **void** Dijkstra(**int** src)\{  
33.     memset(vis, 0, **sizeof**(vis));  
34.     **for**(**int** i=1; i<=n; ++i) d\[i\] = INF;  
35.     d\[src\] = 0;  
36.     q.push(make\_pair(d\[src\], src));  
37.     **while**(!q.empty())\{  
38.         pii u = q.top(); q.pop();  
39.         **int** x = u.second;  
40.         **if**(vis\[x\]) **continue**;  
41.         vis\[x\] = **true**;  
42.         **for**(**int** e = first\[x\]; e!=-1; e=next\[e\]) **if**(d\[v\[e\]\] > d\[x\]+w\[e\])\{  
43.             d\[v\[e\]\] = d\[x\] + w\[e\];  
44.             q.push(make\_pair(d\[v\[e\]\], v\[e\]));  
45.         \}   
46.     \}  
47. \}  
48.     
49. **int** main()\{  
50.     **int** a,b,c;  
51.     **while**(~scanf("%d%d",&n,&m)&&n+m)\{  
52.         read\_graph();  
53.         Dijkstra(1);  
54.         printf("%d\\n", d\[n\]);  
55.     \}  
56.     **return** 0;  
57. \}

**3. Dijkstra+邻接表(用vecor实现)+优先队列优化**

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include<cstdio>  
2.  \#include<cstring>  
3.  \#include<utility>  
4.  \#include<queue>  
5.  \#include<vector>  
6.  **using** **namespace** std;  
7.      
8.  **const** **int** N=105;  
9.  **const** **int** INF=9999999;  
10.     
11. **typedef** pair<**int**,**int**>pii;  
12. vector<pii>G\[N\];  
13. priority\_queue<pii, vector<pii>, greater<pii> >q;  
14.     
15. **int** d\[N\], first\[N\], u\[N\], v\[N\], w\[N\], next\[N\],n,m;  
16. **bool** vis\[N\];  
17.     
18.     
19. // 无向图的输入，注意没输入的一条边要看作是两条边  
20. **void** read\_graph()\{  
21.     **for**(**int** i=1; i<=n; ++i)  
22.         G\[i\].clear();  
23.     **int** a,b,c;  
24.     **for**(**int** i=1; i<=m; ++i)\{  
25.         scanf("%d%d%d",&a,&b,&c);  
26.         G\[a\].push\_back(make\_pair(b,c));  
27.         G\[b\].push\_back(make\_pair(a,c));  
28.     \}  
29. \}  
30.     
31. **void** Dijkstra(**int** src)\{  
32.     memset(vis, 0, **sizeof**(vis));  
33.     **for**(**int** i=1; i<=n; ++i) d\[i\] = INF;  
34.     d\[src\] = 0;  
35.     q.push(make\_pair(d\[src\], src));  
36.     **while**(!q.empty())\{  
37.         pii t = q.top(); q.pop();  
38.         **int** u = t.second;  
39.         **if**(vis\[u\]) **continue**;  
40.         vis\[u\] = **true**;  
41.         **for**(**int** v=0; v<G\[u\].size(); ++v)**if**(d\[G\[u\]\[v\].first\] > d\[u\]+G\[u\]\[v\].second)\{  
42.             d\[G\[u\]\[v\].first\] = d\[u\]+G\[u\]\[v\].second;  
43.             q.push(make\_pair(d\[G\[u\]\[v\].first\], G\[u\]\[v\].first));  
44.         \}  
45.     \}  
46. \}  
47.     
48. **int** main()\{  
49.     **int** a,b,c;  
50.     **while**(~scanf("%d%d",&n,&m)&&n+m)\{  
51.         read\_graph();  
52.         Dijkstra(1);  
53.         printf("%d\\n", d\[n\]);  
54.     \}  
55.     **return** 0;  
56. \}

**二，Bellman-Ford算法**

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include<cstdio>  
2.  \#include<cstring>  
3.  \#include<utility>  
4.  \#include<queue>  
5.  **using** **namespace** std;  
6.      
7.  **const** **int** N=20005;  
8.  **const** **int** INF=9999999;  
9.      
10. **int** n, m, u\[N\],v\[N\],w\[N\], d\[N\];  
11.     
12.     
13. // 无向图的输入，注意每输入的一条边要看作是两条边  
14. **inline** **void** read\_graph()\{  
15.     **for**(**int** e=1; e<=m; ++e)\{  
16.         scanf("%d%d%d",&u\[e\],&v\[e\],&w\[e\]);  
17.     \}  
18. \}  
19.     
20. **inline** **void** Bellman\_Ford(**int** src)\{  
21.     **for**(**int** i=1; i<=n; ++i) d\[i\] = INF;  
22.     d\[src\] = 0;  
23.     **for**(**int** k=0; k<n-1; ++k)\{  
24.         **for**(**int** i=1; i<=m; ++i)\{   
25.             **int** x=u\[i\], y=v\[i\];  
26.             **if**(d\[x\] < INF)\{  
27.                 **if**(d\[y\]>d\[x\]+w\[i\])  
28.                     d\[y\] = d\[x\]+w\[i\];  
29.             \}  
30.             **if**(d\[y\] < INF)\{  
31.                 **if**(d\[x\]>d\[y\]+w\[i\])  
32.                     d\[x\] = d\[y\]+w\[i\];  
33.             \}  
34.         \}  
35.     \}  
36. \}  
37.     
38. **int** main()\{  
39.     **int** a,b,c;  
40.     **while**(~scanf("%d%d",&n,&m)&&n+m)\{  
41.         read\_graph();  
42.         Bellman\_Ford(1);  
43.         printf("%d\\n", d\[n\]);  
44.     \}  
45.     **return** 0;  
46. \}

**三，****SPFA**

邻接表实现

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include<cstdio>  
2.  \#include<cstring>  
3.  \#include<utility>  
4.  \#include<queue>  
5.  **using** **namespace** std;  
6.      
7.  **const** **int** N=20005;  
8.  **const** **int** INF=2147483646>>1;  
9.      
10. **int** n, m, first\[N\],next\[N\],u\[N\],v\[N\],w\[N\], d\[N\];  
11. **bool** vis\[N\];  
12.     
13. queue<**int**>q;  
14.     
15. **inline** **void** read\_graph()\{  
16.     memset(first, -1, **sizeof**(first));  
17.     **for**(**int** e=1; e<=m; ++e)\{  
18.         scanf("%d%d%d",&u\[e\],&v\[e\],&w\[e\]);  
19.         u\[e+m\]=v\[e\], v\[e+m\]=u\[e\], w\[e+m\]=w\[e\];  
20.         next\[e\] = first\[u\[e\]\];  
21.         first\[u\[e\]\] = e;  
22.         next\[e+m\] = first\[u\[e+m\]\];  
23.         first\[u\[e+m\]\] = e+m;  
24.     \}  
25. \}  
26.     
27. **void** SPFA(**int** src)\{  
28.     memset(vis, 0, **sizeof**(vis));  
29.     **for**(**int** i=1; i<=n; ++i) d\[i\] = INF;  
30.     d\[src\] = 0;  
31.     vis\[src\] = **true**;  
32.     
33.     q.push(src);  
34.     **while**(!q.empty())\{  
35.         **int** x = q.front();  q.pop();  
36.         vis\[x\] = **false**;  
37.         **for**(**int** e=first\[x\]; e!=-1; e=next\[e\])\{  
38.             **if**(d\[x\]+w\[e\] < d\[v\[e\]\])\{  
39.                 d\[v\[e\]\] = d\[x\]+w\[e\];  
40.                 **if**(!vis\[v\[e\]\])\{  
41.                     vis\[v\[e\]\] = **true**;  
42.                     q.push(v\[e\]);  
43.                 \}  
44.             \}  
45.         \}  
46.     \}   
47. \}  
48.     
49. **int** main()\{  
50.     **int** a,b,c;  
51.     **while**(~scanf("%d%d",&n,&m)&&n+m)\{  
52.         read\_graph();  
53.         SPFA(1);  
54.         printf("%d\\n", d\[n\]);  
55.     \}  
56.     **return** 0;  
57. \}

四， Floyd算法

**\[cpp\]** [view plain][][copy][view plain]

1.  \#include<cstdio>  
2.  \#include<cstring>  
3.  \#include<utility>  
4.  \#include<queue>  
5.  **using** **namespace** std;  
6.      
7.  **const** **int** N=105;  
8.  **const** **int** INF=2147483646;  
9.      
10. **int** n, m, d\[N\]\[N\];  
11.     
12.     
13. **inline** **void** read\_graph()\{  
14.     **for**(**int** i=1; i<=n; ++i)\{  
15.         d\[i\]\[i\] = INF;  
16.         **for**(**int** j=i+1; j<=n; ++j)  
17.             d\[i\]\[j\]=d\[j\]\[i\]=INF;  
18.     \}  
19.     **int** a,b,c;  
20.     **for**(**int** e=1; e<=m; ++e)\{  
21.         scanf("%d%d%d",&a,&b,&c);  
22.         d\[a\]\[b\]=d\[b\]\[a\]=c;  
23.     \}  
24. \}  
25.     
26. **inline** **void** Floyd(**int** src)\{  
27.     **for**(**int** k=1; k<=n; ++k)\{  
28.         **for**(**int** i=1; i<=n; ++i)\{  
29.             **for**(**int** j=1; j<=n; ++j)  
30.                 **if**(d\[i\]\[k\]<INF && d\[k\]\[j\]<INF)\{  //防止溢出  
31.                     d\[i\]\[j\] = min(d\[i\]\[j\], d\[i\]\[k\]+d\[k\]\[j\]);  
32.                 \}  
33.         \}  
34.     \}  
35. \}  
36.     
37. **int** main()\{  
38.     **int** a,b,c;  
39.     **while**(~scanf("%d%d",&n,&m)&&n+m)\{  
40.         read\_graph();  
41.         Floyd(1);  
42.         printf("%d\\n", d\[1\]\[n\]);  
43.     \}  
44.     **return** 0;  
45. \}

[http_acm.hdu.edu.cn_showproblem.php_pid_2544]: http://acm.hdu.edu.cn/showproblem.php?pid=2544
[UESTC 6th Programming Contest Online]: http://acm.hdu.edu.cn/search.php?field=problem&key=UESTC%206th%20Programming%20Contest%20Online&source=1&searchmode=source
[http_blog.csdn.net_shuangde800]: http://blog.csdn.net/shuangde800
[view plain]: http://blog.csdn.net/shuangde800/article/details/7987134