原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1874
畅通工程续
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 27465 Accepted Submission(s): 9914
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),分别代表起点和终点。
每组数据第一行包含两个正整数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
Author
linle
Source
Recommend
分析:这道题目求最短路,用SPFA,就可以解决。
1.建图
void add_edge(int a,int b,int c) { v[e] = b; //第e条边指向b这个顶点 w[e] = c; //第e条边权值为c next[e] = first[a]; //e边的下一天边就是从a点出发的第一条边 first[a] = e++; //于是这时从a点出发的第一条边就是e了 }2.SPFA
void spfa(int st) { //初始化路径和数组为无穷大 memset(d,0x3f,sizeof(d)); //起点路径和为0 d[st] = 0; //入队,则标记为true; inq[st] = true; q.push(st); while(!q.empty()) { //队头顶点 int u = q.front(); q.pop(); inq[u] = 0; //遍历与它所有相邻的路径 for(int i=first[u];i!= -1;i=next[i]) { //松弛操作 if(d[v[i]]>d[u]+w[i]) { d[v[i]] = d[u]+w[i]; if(!inq[v[i]])q.push(v[i]),inq[v[i]] = true; } } } }3.结果
printf("%d\n",d[t]==INF?-1:d[t]);
完整代码:
#include<cstdio> #include<cstring> #include<queue> using namespace std; #define MAXN 2010 #define MAXNF 210 #define INF 0x3f3f3f3f int n,m,e,a,b,c,s,t; queue<int> q; int v[MAXN],d[MAXN],next[MAXN],w[MAXN],first[MAXNF]; bool inq[MAXNF]; void init() { e = 0; memset(first,-1,sizeof(first)); } void add_edge(int a,int b,int c) { v[e] = b; w[e] = c; next[e] = first[a]; first[a] = e++; } void spfa(int st) { //初始化路径和数组为无穷大 memset(d,0x3f,sizeof(d)); //起点路径和为0 d[st] = 0; //入队,则标记为true; inq[st] = true; q.push(st); while(!q.empty()) { //队头顶点 int u = q.front(); q.pop(); inq[u] = 0; //遍历与它所有相邻的路径 for(int i=first[u];i!= -1;i=next[i]) { //松弛操作 if(d[v[i]]>d[u]+w[i]) { d[v[i]] = d[u]+w[i]; if(!inq[v[i]])q.push(v[i]),inq[v[i]] = true; } } } } int main() { while(~scanf("%d%d",&n,&m)) { init(); for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); add_edge(a,b,c); add_edge(b,a,c); } scanf("%d%d",&s,&t); spfa(s); printf("%d\n",d[t]==INF?-1:d[t]); } return 0; }
相关推荐
题目链接题目意思有n个城镇,编号为0~n-1,m条道路,从一个城镇到另一个城镇有多条路,现在问你从一个城镇到另一个城镇的最短距离是多少。其中要注意的是,城镇之间
算法-畅通工程续(HDU-1874)(包含源程序).rar
NULL 博文链接:https://128kj.iteye.com/blog/1716470
算法-畅通工程(HDU-1232)(包含源程序).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码
ACM HDU题目分类,我自己总结的大概只有十来个吧
自己做的HDU ACM已经AC的题目
HDU最全ac代码
hdu动态规划算法集锦