HDU 1874 畅通工程续 (Dijkstra , Floyd , SPFA, Bellman_Ford 四种算法)

矫情吗；* 2022-08-09 13:46 139阅读 0赞

**畅通工程续**

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1874][http_acm.hdu.edu.cn_showproblem.php_pid_1874]

Problem Description

某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。  
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。

Input

本题目包含多组数据，请处理到文件结束。每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。

Output

对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出\-1.

Sample Input

3 3

0 1 1

0 2 3

1 2 1

0 2

3 1

0 1 1

1 2

Sample Output

\-1

Author

linle

Source

[2008浙大研究生复试热身赛（2）——全真模拟][2008_2]

解法一：Dijkstra算法

![HDU 1874 畅通工程续 (Dijkstra , Floyd , SPFA, Bellman\_Ford 四种算法) - AcBoy - AcBoy的博客][HDU 1874 _ _Dijkstra _ Floyd _ SPFA_ Bellman_Ford _ - AcBoy - AcBoy]

\#include<iostream>

\#include<cstdio>

\#include<cstring>

usingnamespace std;

constint INF=0x3f3f3f3f;

constint N=210;

int n,m,s,t;

int map\[N\]\[N\],dis\[N\],vis\[N\];

void Dijkstra(int src)\{

int i;

for(i=0;i<n;i++)\{

dis\[i\]=map\[src\]\[i\];

vis\[i\]=0;

dis\[src\]=0;

vis\[src\]=1;

int j,k,tmp;

for(i=0;i<n;i++)\{

tmp=INF;

for(j=0;j<n;j++)

if(!vis\[j\] && tmp>dis\[j\])\{

k=j;

tmp=dis\[j\];

if(tmp==INF)

break;

vis\[k\]=1;

for(j=0;j<n;j++)

if(!vis\[j\] && dis\[j\]>dis\[k\]+map\[k\]\[j\])

dis\[j\]=dis\[k\]+map\[k\]\[j\];

int main()\{

//freopen("input.txt","r",stdin);

while(~scanf("%d%d",&n,&m))\{

int u,v,w;

for(int i=0;i<n;i++)

for(int j=0;j<n;j++)

map\[i\]\[j\]=INF;

for(int i=0;i<m;i++)\{

scanf("%d%d%d",&u,&v,&w);

if(map\[u\]\[v\]>w)

map\[u\]\[v\]=map\[v\]\[u\]=w;

scanf("%d%d",&s,&t);

Dijkstra(s);

if(dis\[t\]==INF)

printf("-1\\n");

else

printf("%d\\n",dis\[t\]);

return0;

![HDU 1874 畅通工程续 (Dijkstra , Floyd , SPFA, Bellman\_Ford 四种算法) - AcBoy - AcBoy的博客][HDU 1874 _ _Dijkstra _ Floyd _ SPFA_ Bellman_Ford _ - AcBoy - AcBoy]

解法二：SPFA算法

![HDU 1874 畅通工程续 (Dijkstra , Floyd , SPFA, Bellman\_Ford 四种算法) - AcBoy - AcBoy的博客][HDU 1874 _ _Dijkstra _ Floyd _ SPFA_ Bellman_Ford _ - AcBoy - AcBoy]

\#include<stdio.h>

\#include<iostream>

\#include<queue>

usingnamespace std;

\#define N 205

\#define INF 99999999

int n,m,map\[N\]\[N\];

int visited\[N\],dis\[N\];

int SPFA(int src,int des)\{

int i;

for(i=0;i<n;i++)\{

dis\[i\]=INF;

visited\[i\]=0;

queue<int> myqueue;

while(!myqueue.empty())

myqueue.pop();

dis\[src\]=0;

visited\[src\]=1;

myqueue.push(src);

int tmp;

while(!myqueue.empty())\{

tmp=myqueue.front();

myqueue.pop();

visited\[tmp\]=0;

for(i=0;i<n;i++)

if(dis\[i\]>dis\[tmp\]+map\[tmp\]\[i\])\{

dis\[i\]=dis\[tmp\]+map\[tmp\]\[i\];

if(!visited\[i\])\{

visited\[i\]=1;

myqueue.push(i);

return dis\[des\];

int main()\{

int u,v,cost;

while(scanf("%d%d",&n,&m)!=EOF)\{

int i,j;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

map\[i\]\[j\]=INF;

for(i=0;i<m;i++)\{

scanf("%d%d%d",&u,&v,&cost);

if(cost<map\[u\]\[v\])

map\[u\]\[v\]=map\[v\]\[u\]=cost;

int s,t;

scanf("%d%d",&s,&t);

int ans=SPFA(s,t);

if(ans<INF)

printf("%d\\n",ans);

else

printf("-1\\n");

return0;

![HDU 1874 畅通工程续 (Dijkstra , Floyd , SPFA, Bellman\_Ford 四种算法) - AcBoy - AcBoy的博客][HDU 1874 _ _Dijkstra _ Floyd _ SPFA_ Bellman_Ford _ - AcBoy - AcBoy]

解法三：Floyd算法

![HDU 1874 畅通工程续 (Dijkstra , Floyd , SPFA, Bellman\_Ford 四种算法) - AcBoy - AcBoy的博客][HDU 1874 _ _Dijkstra _ Floyd _ SPFA_ Bellman_Ford _ - AcBoy - AcBoy]

\#include<iostream>

\#include<queue>

\#include<cstdio>

\#include<cstring>

usingnamespace std;

constint INF=0x3f3f3f3f;

constint N=210;

int n,m;

int map\[N\]\[N\];

void Floyd()\{

int i,j,k;

for(k=0;k<n;k++)

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(map\[i\]\[j\]>map\[i\]\[k\]+map\[k\]\[j\])

map\[i\]\[j\]=map\[i\]\[k\]+map\[k\]\[j\];

int main()\{

//freopen("input.txt","r",stdin);

while(~scanf("%d%d",&n,&m))\{

int i,j;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

map\[i\]\[j\]=(i==j?0:INF); //注意自身和自身距离为0。

int u,v,w;

for(i=0;i<m;i++)\{

scanf("%d%d%d",&u,&v,&w);

if(map\[u\]\[v\]>w)

map\[u\]\[v\]=map\[v\]\[u\]=w;

int s,t;

scanf("%d%d",&s,&t);

Floyd();

if(map\[s\]\[t\]==INF)

printf("-1\\n");

else

printf("%d\\n",map\[s\]\[t\]);

return0;

![HDU 1874 畅通工程续 (Dijkstra , Floyd , SPFA, Bellman\_Ford 四种算法) - AcBoy - AcBoy的博客][HDU 1874 _ _Dijkstra _ Floyd _ SPFA_ Bellman_Ford _ - AcBoy - AcBoy]

Bellman\_Ford

![HDU 1874 畅通工程续 (Dijkstra , Floyd , SPFA, Bellman\_Ford 四种算法) - AcBoy - AcBoy的博客][HDU 1874 _ _Dijkstra _ Floyd _ SPFA_ Bellman_Ford _ - AcBoy - AcBoy]

\#include<iostream>

\#include<queue>

\#include<cstdio>

\#include<cstring>

usingnamespace std;

constint INF=0x3f3f3f3f;

constint N=210;

int n,m,cnt;

int dis\[N\];

struct node\{

int u,v;

int w;

\}edge\[1010\*2\];

void addedge(int u,int v,int w)\{

edge\[cnt\].u=u; edge\[cnt\].v=v; edge\[cnt\].w=w;

cnt++;

edge\[cnt\].u=v; edge\[cnt\].v=u; edge\[cnt\].w=w;

cnt++;

int Bellman\_Ford(int src,int des)\{

int i,k;

for(i=0;i<n;i++)

dis\[i\]=INF;

dis\[src\]=0;

for(k=0;k<n-1;k++)

for(i=0;i<cnt;i++)

if(dis\[edge\[i\].u\]!=INF && dis\[edge\[i\].v\]>dis\[edge\[i\].u\]+edge\[i\].w)

dis\[edge\[i\].v\]=dis\[edge\[i\].u\]+edge\[i\].w;

return dis\[des\]==INF?-1:dis\[des\];

int main()\{

//freopen("input.txt","r",stdin);

while(~scanf("%d%d",&n,&m))\{

cnt=0;

int u,v,w;

for(int i=0;i<m;i++)\{

scanf("%d%d%d",&u,&v,&w);

addedge(u,v,w);

int s,t;

scanf("%d%d",&s,&t);

printf("%d\\n",Bellman\_Ford(s,t));

return0;

![HDU 1874 畅通工程续 (Dijkstra , Floyd , SPFA, Bellman\_Ford 四种算法) - AcBoy - AcBoy的博客][HDU 1874 _ _Dijkstra _ Floyd _ SPFA_ Bellman_Ford _ - AcBoy - AcBoy]

在网上搜索得到的，觉得写得挺好，自己也总结不了那么全，就先转载过来！

原文链接：[http://www.cnblogs.com/jackge/archive/2013/01/01/2841536.html][http_www.cnblogs.com_jackge_archive_2013_01_01_2841536.html]

[http_acm.hdu.edu.cn_showproblem.php_pid_1874]: http://acm.hdu.edu.cn/showproblem.php?pid=1874
[2008_2]: http://www.cnblogs.com/search.php?field=problem&key=2008浙大研究生复试热身赛（2）——全真模拟&source=1&searchmode=source
[HDU 1874 _ _Dijkstra _ Floyd _ SPFA_ Bellman_Ford _ - AcBoy - AcBoy]: http://img1.ph.126.net/SR-ZTUNX3Y6IA5xqnQ9Vhg==/3099320968578640033.jpg
[http_www.cnblogs.com_jackge_archive_2013_01_01_2841536.html]: http://www.cnblogs.com/jackge/archive/2013/01/01/2841536.html