畅通工程续
Time Limit: 3000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11311Accepted Submission(s): 3791
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
#include<stdio.h>
#include<string.h>
int n,m,start,end,map[205][205],used[205],min[205],mm,temp;
int find_short()
{
int i,j;
memset(used,0,sizeof(used));
used[start]=1;
for(i=0;i<n;i++)
min[i]=map[start][i];
min[start]=0;//这里是加上去的 但是不加也对 不过还是加上的好
for(i=1;i<n;i++)//此处是限制次数
{
mm=999999999;
for(j=0;j<n;j++)
{
if(!used[j]&&mm>min[j])
{
temp=j;
mm=min[j];
}
}
/*if(temp==end) {printf("%d\n",mm);return 0;}
if(mm==999999999) {printf("-1\n");return 0;}
上面的输出方法是绝对错误的因为对于如start和end相同的这种情况 最后把所有点都找完了 也不会找到temp==end 而此时mm为999999999
而实际上应该是0 所以应该是把所有的点全部给找出来后再去判断 如果不存在从start到end的路 那么min[end]一定是99999999无穷大*/
if(temp==end||mm==999999999) break; //提前退出
used[temp]=1;
for(j=0;j<n;j++)
{
if(!used[j]&&min[temp]+map[temp][j]<min[j])//min[temp]+map[temp][j]不是mm+map[temp][j]
min[j]=min[temp]+map[temp][j];
}
}
return min[end];
}
int main()
{
int i,j,x,y,z,k;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(i=0;i<n+2;i++)
for(j=0;j<n+2;j++)
map[i][j]=999999999;
for(i=0;i<m;i++)
{
scanf("%d %d %d",&x,&y,&z);
if(z<map[x][y])//居然有重边 出题人无聊 操
map[x][y]=map[y][x]=z;
}
for(i=0;i<n;i++)
map[i][i]=0;
scanf("%d %d",&start,&end);
k=find_short();
if(k==999999999) printf("-1\n");
else printf("%d\n",k);
}
return 0;
}
分享到:
相关推荐
适合于单源最短路径算法,采用的是dijkstra最短路径算法。简单易懂,本题在hdu.edu.cn上通过了,网址是http://acm.hdu.edu.cn/search.php?field=problem&key=2680。由于不能同时上传两个文件,所以我放到另一个去了...
题目链接题目意思有n个城镇,编号为0~n-1,m条道路,从一个城镇到另一个城镇有多条路,现在问你从一个城镇到另一个城镇的最短距离是多少。其中要注意的是,城镇之间
最短路径 贪心实现代码 hdu 最短路 dijkstra 算法
SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称,通常用于求含负权边的单源最短路径,以及判负权环。SPFA 最坏情况下复杂度和朴素 Bellman-Ford 相同,为 O(VE)。
算法-畅通工程续(HDU-1874)(包含源程序).rar
NULL 博文链接:https://128kj.iteye.com/blog/1716470
算法-畅通工程(HDU-1232)(包含源程序).rar
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码