首页 > 代码库 > zoj 1891 - 传说中的简答题 - 最短路径 - dijkstra
zoj 1891 - 传说中的简答题 - 最短路径 - dijkstra
在复习资料中找到的对应不同类型的题目。想先从简单的题目入手,结果一上来就发现不对劲。感觉有点不简单呀。
之前也是碰到这种问题会畏首畏尾,因为,要计算两点之间的距离的。想着要不要先全部计算出来,放到数组里面分别调用。
但后来又想到不行,这样的时间复杂度更高了,n*(n+1)/2 的时间复杂度。就有点麻乱了。
通过参考网上其他的解答,发现他们也是一边算,一边找的。相比这就是简答题的优势吧。
然后题目的要求是求出最小花费的时间,这几天刚好在复习dijkstra算法。就可以用上了。
这里稍微总结一下:
算法总路线: 以出发点作为最短路径的集合flag,不断的寻找剩余点里面的最短路径,一个一个加入到最短路径集合flag中,并且更新出发点到各个点的最小距离dis。
1、初始化出发点到各个点的最小距离数组dis。这里直接根据各个节点map来计算。
2、总共n个结点,进行n次大循环,依次加入当前状态下最小的结点。
2.1、 通过n次贪心算法,寻找当前状态离出发点的最短距离点;
2.2、标记最短距离点,加入最短路径的集合flag;
2.3、以找到的结点为中介,更新最短路径集合flag。 即比较出 sta-->j & sta-->pos-->j 这两种方式哪个最短。
上链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=891
/* http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=891 1、对输入的节点分别录入,并根据线路标记分类; 2、利用dijkstra求出最少花费路径。 确实是要分别计算两个点之间的距离的。 dijkstra。循环计算从出发节点到其他节点的最短距离。 */ #include <stdio.h> #include <math.h> #define M 202 #define INF 0x3f3f3f3f typedef struct { double x,y; }NODE; NODE point[M]; int flag[M]; int cate[M];//在一条线上 double dis[M]; //fl == 1 ,walk; 2,subway double calc(NODE a, NODE b,int fl)// sqrt( a*a+b*b ) { double tmp1 = (a.x-b.x)*(a.x-b.x); double tmp2 = (a.y-b.y)*(a.y-b.y); if( fl == 1) return sqrt(tmp1+tmp2)/10000*60.0; return sqrt(tmp1+tmp2)/40000*60.0; } //应该多注意的一点,用来添加最短路径的点循环中,i的作用就是计数, //用不着它在循环中做判断 void dijkstra(int sta,int n) { int i,j; for(i=0 ;i< n; i++) { flag[i] = 0; } for(i=1 ; i<n ;i++) { dis[i] = calc( point[sta], point[i], 1); } flag[sta] = 1; for(i=1 ; i<n ;i++)//循环一次加入每一个点 { double min = INF; int pos; for(j=1 ; j<n ; j++)//n-1次贪心 { if( flag[j] == 1)continue; if( dis[j] < min ) { min = dis[j]; pos = j; } } flag[pos] = 1; dis[pos] = min; for(j=1 ; j<n; j++) { if( flag[j] == 1) continue; double t1 = dis[pos];//pos -- j ,'s distance if( cate[pos] == cate[j] && ( pos==j-1 || j==pos-1) )// 中介比较的点是pos,不是i。这里注意 t1 += calc(point[pos],point[j],2); //相邻而且在 一条subway上的使用subway方法 else t1 += calc(point[pos],point[j],1); if( t1 < dis[j] ) dis[j] = t1; } } } int main() { int i,j; double x,y; while(scanf("%lf%lf", &x, &y) != EOF) { if( x==-1 && y==-1) break; point[0].x= x; point[0].y= y; scanf("%lf%lf",&point[1].x, &point[1].y); cate[0] = 0;//这个时候假设起点、终点与任何一个地铁线路的站台都不在一起 cate[1] = 1; i=2; j=2; while( scanf("%lf%lf", &x, &y) && (x!=-1) && (y!=-1)) { cate[i] = j; point[i].x = x; point[i++].y = y; while( scanf("%lf%lf", &x, &y) && (x!=-1) && y!=-1) { cate[i] = j; point[i].x = x; point[i++].y= y; } j++; } /* for(j=0 ; j<i ;j++) printf("[%d,%d],", point[j].x, point[j].y);*/ dijkstra(0,i); printf("%.0lf\n", dis[1]); } return 0; }
一次就AC了之后还是很激动的说。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。