HUD 1874 畅通工程续(Dijkstra/spfa/floyd)

2024-04-16 11:18
文章标签 工程 spfa 畅通 dijkstra floyd hud 1874

本文主要是介绍HUD 1874 畅通工程续(Dijkstra/spfa/floyd)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 
  
2
-1
版本一：Floyd（时间复杂度O(n^3)） 
<span style="font-size:10px;">//Must so
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<ctype.h>
#include<queue>
#include<vector>
#include<set>
#include<cstdio>
#include<cmath>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf 1<<25
#define NN 1000006
using namespace std;
const double PI = acos(-1.0);
typedef long long LL;/**********************************************************************
练手很好，可以尝试 Dijkstra ,spfa,Floyd
尝试1：Floyd
**********************************************************************/
int s,t;//起点和终点
int n,m;//n个点，m条边
int d[202][202];
void init()
{for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){d[i][j] = inf;}d[i][i] = 0;}
}
void floyd()
{for (int k = 0; k < n; k++){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){d[i][j] = min(d[i][j],d[i][k]+d[k][j]);}}}
}
int main()
{while (cin>>n>>m){init();for (int i = 0,u,v,w; i < m; i++){scanf("%d%d%d",&u,&v,&w);if (w < d[u][v]){d[u][v] = w;d[v][u] = w;//双向}}cin>>s>>t;floyd();if (d[s][t] == inf){puts("-1");}else{printf("%d\n",d[s][t]);}}return 0;
}</span><span style="font-size:18px;">
</span>
版本二：SPFA(不定长数组的邻接矩阵实现) 
<span style="font-size:10px;">//Must so
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<ctype.h>
#include<queue>
#include<vector>
#include<set>
#include<cstdio>
#include<cmath>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf 1<<25
#define NN 1000006
using namespace std;
const double PI = acos(-1.0);
typedef long long LL;/**********************************************************************
练手很好，可以尝试 Dijkstra ,spfa,Floyd
尝试2：SPFA(不定长数组实现邻接矩阵)
**********************************************************************/
int s,t;//起点和终点
int n,m;//n个点，m条边
struct Node
{int v,w;
}a;
bool vis[202];
vector<Node>u[202];
queue<int>q;
int d[202];
void spfa()
{for (int i = 0;i < n;i++)d[i] = inf;mem(vis,0);q.push(s);vis[s] = 1;d[s] = 0;//源点最先入队并标记while (!q.empty()){int head = q.front();//取队首元素q.pop();vis[head] = 0;for (int i = 0;i < u[head].size();i++){if (d[ u[head][i].v ] > d[head] + u[head][i].w)//松弛成功{d[ u[head][i].v ] = d[head] + u[head][i].w;//更新值if (vis[u[head][i].v] == 0){q.push(u[head][i].v);//入队vis[u[head][i].v] = 1;}}}}
}
int main()
{while (cin>>n>>m){for (int i = 0;i < n;i++)//不定长数组记得清空u[i].clear();for (int i = 0,uu; i < m; i++){scanf("%d%d%d",&uu,&a.v,&a.w);u[uu].push_back(a);Node b;b.v = uu,b.w = a.w;u[a.v].push_back(b);}cin>>s>>t;spfa();if (d[t] == inf) puts("-1");else printf("%d\n",d[t]);}return 0;
}
</span>


版本三：SPFA（二维数组实现邻接矩阵，这题点少，用二维数组时间反而比不定长数组少） 
<span style="font-size:10px;">//Must so
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<ctype.h>
#include<queue>
#include<vector>
#include<set>
#include<cstdio>
#include<cmath>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf 1<<25
#define NN 1000006
using namespace std;
const double PI = acos(-1.0);
typedef long long LL;/**********************************************************************
练手很好，可以尝试 Dijkstra ,spfa,Floyd
尝试2：SPFA(二维数组实现邻接矩阵)
**********************************************************************/
int s,t;//起点和终点
int n,m;//n个点，m条边
bool vis[202];
int mp[202][202];
queue<int>q;
int d[202];
void spfa()
{for (int i = 0; i < n; i++)d[i] = inf;mem(vis,0);q.push(s);vis[s] = 1;d[s] = 0;//源点最先入队并标记while (!q.empty()){int head = q.front();//取队首元素q.pop();vis[head] = 0;for (int i = 0; i < n; i++){if (d[i] > d[head] + mp[head][i])//松弛成功{d[i] = d[head] + mp[head][i];//更新值if (vis[i] == 0){q.push(i);//入队vis[i] = 1;}}}}
}
int main()
{while (cin>>n>>m){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){mp[i][j] = inf;}mp[i][i] = 0;}for (int i = 0,uu,vv,ww; i < m; i++){scanf("%d%d%d",&uu,&vv,&ww);if (ww < mp[uu][vv]){mp[uu][vv] = ww,mp[vv][uu] = ww;}}cin>>s>>t;spfa();if (d[t] == inf) puts("-1");else printf("%d\n",d[t]);}return 0;
}
</span>

版本四：SPFA（邻接表实现） 

//Must so
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<ctype.h>
#include<queue>
#include<vector>
#include<set>
#include<cstdio>
#include<cmath>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf 1<<25
#define NN 1000006
using namespace std;
const double PI = acos(-1.0);
typedef long long LL;/**********************************************************************
练手很好，可以尝试 Dijkstra ,spfa,Floyd
尝试2：SPFA(邻接表实现)
**********************************************************************/
int s,t;//起点和终点
int n,m;//n个点，m条边
struct Node
{int v,w,next;
}e[2002];//因为双向的原因边最多有2000条
int h[102];
bool vis[202];
queue<int>q;
int d[202];
void spfa()
{for (int i = 0; i < n; i++)d[i] = inf;mem(vis,0);q.push(s);vis[s] = 1;d[s] = 0;//源点最先入队并标记while (!q.empty()){int head = q.front();//取队首元素q.pop();vis[head] = 0;for (int i = h[head]; i != -1; i = e[i].next){if (d[e[i].v ] > d[head] +e[i].w)//松弛成功{d[e[i].v ] = d[head] + e[i].w;//更新值if (vis[e[i].v] == 0){q.push(e[i].v);//入队vis[e[i].v] = 1;}}}}
}
int main()
{while (cin>>n>>m){mem(h,-1);int o = 0;for (int i = 0,uu,vv,ww; i < m; i++){scanf("%d%d%d",&uu,&vv,&ww);e[o].v = vv;e[o].w = ww;e[o].next = h[uu];h[uu] = o++;e[o].v = uu;e[o].w = ww;e[o].next = h[vv];h[vv] = o++;}cin>>s>>t;spfa();if (d[t] == inf) puts("-1");else printf("%d\n",d[t]);}return 0;
}
版本五：Dijkstra 
//Must so
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<ctype.h>
#include<queue>
#include<vector>
#include<set>
#include<cstdio>
#include<cmath>
#define mem(a,x) memset(a,x,sizeof(a))
#define inf 1<<25
#define NN 1000006
using namespace std;
const double PI = acos(-1.0);
typedef long long LL;/**********************************************************************
练手很好，可以尝试 Dijkstra ,spfa,Floyd
尝试3：Dijkstra
**********************************************************************/
int s,t;//起点和终点
int n,m;//n个点，m条边
bool vis[202];
int d[202];
int mp[202][202];
void Dijk()
{mem(vis,0);for (int i = 0; i < n; i++){int mn = inf,pos;for (int j = 0; j < n; j++){if (d[j] < mn&&vis[j] == 0){mn = d[j];pos = j;}}vis[pos] = 1;for (int j = 0; j < n; j++){d[j] = min(d[j],d[pos]+mp[pos][j]);}}
}
int main()
{while (cin>>n>>m){for (int i = 0;i < n;i++){for (int j = 0;j < n;j++){mp[i][j] = inf;}mp[i][i] = 0;d[i] = inf;}for (int i = 0,uu,vv,ww; i < m; i++){scanf("%d%d%d",&uu,&vv,&ww);if (ww < mp[uu][vv]){mp[uu][vv] = ww,mp[vv][uu] = ww;}}cin>>s>>t;d[s] = 0;Dijk();if (d[t] == inf) puts("-1");else printf("%d\n",d[t]);}return 0;
}



这篇关于HUD 1874 畅通工程续(Dijkstra/spfa/floyd)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/908640。

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
poj 1511 Invitation Cards(spfa最短路)

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离，求来回到点1的最短路中的边权和。 因为边很大，不能用原来的dijkstra什么的，所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码： #include<stdio.h>#include<stack>using namespace std;const int M
阅读更多...
poj 1502 MPI Maelstrom（单源最短路dijkstra）

poj 1502 MPI Maelstrom（单源最短路dijkstra）

题目真是长得头疼，好多生词，给跪。 没啥好说的，英语大水逼。 借助字典尝试翻译了一下，水逼直译求不喷 Description： BIT他们的超级计算机最近交货了。（定语秀了一堆词汇那就省略吧再见） Valentine McKee的研究顾问Jack Swigert，要她来测试一下这个系统。 Valentine告诉Swigert：“因为阿波罗是一个分布式共享内存的机器，所以它的内存访问
阅读更多...
uva 10801（乘电梯dijkstra）

uva 10801（乘电梯dijkstra）

题意： 给几个电梯，电梯0 ~ n-1分别可以到达很多层楼。 换乘电梯需要60s时间。 问从0层到target层最小的时间。 解析： 将进入第0层的电梯60s也算上，最后减。 坑点是如果target为0输出0。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algori
阅读更多...
uva 10099（floyd变式）

uva 10099（floyd变式）

题意： 有一个导游要带着一群旅客从一个城市到达另一个城市，每个城市之间有最大的旅客流量限制。 问最少几趟能将这些旅客从一个城市搞到另一个城市。 解析： 用floyd找出最小流量中的最大边，然后次数就是   ceil（总人数 / 最大承载量 - 1），-1的意思是导游每次也要在车上。 ps.老司机哭晕在厕所 代码： #include <iostream>#includ
阅读更多...
uva 10048(floyd变式）

uva 10048(floyd变式）

题意： 求两个点之间经过的路径中最大噪声最小的值。 解析： floyd的变式，每次取g[i][k] g[k][j]中的大边与当前边g[i][j]比较，取小。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#includ
阅读更多...
poj 3159 （spfa差分约束最短路） poj 1201

poj 3159 （spfa差分约束最短路） poj 1201

poj 3159: 题意： 每次给出b比a多不多于c个糖果，求n最多比1多多少个糖果。 解析： 差分约束。 这个博客讲差分约束讲的比较好： http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。 代码： #include <iostream>#include <cstdio>#i
阅读更多...
poj 1734 （floyd求最小环并打印路径）

poj 1734 （floyd求最小环并打印路径）

题意： 求图中的一个最小环，并打印路径。 解析： ans 保存最小环长度。 一直wa，最后终于找到原因，inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用，但是还是有局限性。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl
阅读更多...
hdu 3790 (单源最短路dijkstra）

hdu 3790 (单源最短路dijkstra）

题意： 每条边都有长度d 和花费p，给你起点s 终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。 解析： 考察对dijkstra的理解。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin
阅读更多...
poj 3169 spfa 差分约束

poj 3169 spfa 差分约束

题意： 给n只牛，这些牛有些关系。 ml个关系：fr 与 to 牛间的距离要小于等于 cost。 md个关系：fr 与 to 牛间的距离要大于等于 cost。 隐含关系： d[ i ] <= d[ i + 1 ] 解析： 用以上关系建图，求1-n间最短路即可。 新学了一种建图的方法。。。。。。 代码： #include <iostream>#include
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2