暑假集训时学了一下Dijkstra算法,当时貌似明白了。昨天学长说让学一下图论,便想着做一道Dijkstra的水题,没想到又重新理解了一下Dijkstra,暑假学得全忘了。。。杯具。。。。。不过这次对Dijkstra又有了一个新的理解,Dijkstra实际上就是个两重循环,只不过是在循环的过程中加入了一些判断条件。。。这也就是为什么时间复杂度是(n*n)的原因。。。。。。。。。。。题目:
某省自从实行了很多年的畅通工程计划后,终于修建了很多路。不过路多了也不好,每次要从一个城镇到另一个城镇时,都有许多种道路方案可以选择,而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在,已知起点和终点,请你计算出要从起点到终点,最短需要行走多少距离。
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
ac代码:
分享到:
相关推荐
本设计以VC++6.0作为程序开发环境,C语言作为程序开发语言,详细介绍了最短路径的求解算法及其C语言实现过程。系统主要实现了图的创建、单源点最短路径的计算功能。依照本系统可以解决实际生活中许多路径选择问题,...
用贪心算法解单源最短路径问题 明确单源最短路径问题的概念;利用贪心算法解决单源最短路径问题;并通过本例熟悉贪心算法在程序设计中的应用方法。
单源最短路径dijkstra模板,做类似的题目可以直接套用,图的存储用邻接矩阵,带有测试数据。
java算法分析与设计之单源最短路径(Dijkstra算法)源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络...
单源最短路径Dijkstra并行程序 单源最短路径Dijkstra串行程序
A、掌握图中单源最短路径的概念; B、掌握Dijkstra算法的原理;
1.分支限界法求解单源最短路径 2.C++源码+程序说明文档 3.源码带详细注释
经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径经典算法单源最短路径
单源最短路径--分支限界法
用C++实现的贪心算法 Dijkstra 单源最短路径,并包含大量的注释,对理解程序很有帮助
图论算法库 C++ 语言实现 代码内容 图论算法库,包括以下算法: 单源最短路径 Dijkstra 算法 单源最短路径 Bellman-Ford 算法 最小生成树 Prim 算法 每对节点间最短路径 Flod-Warshall 算法
用python实现迪杰斯特拉算法,单源最短路径,有向图权值无负值,用邻接矩阵来存储有向图,实现路径存储和路径打印
单元最短路径,为广大计算机专业学生算法所需实验报告而准备
算法设计与分析实验报告,附已通过源码,供学习参考,共勉♪ 目录摘要如下: 1.问题描述 2.实验目的 3.实验原理 4.实验设计 (包括输入格式、算法、输出格式) 5.实验结果与分析 (除了截图外,实验结果还用...
单源最短路径——算法 单源最短路径——算法 单源最短路径——算法
有很长时间没有上传了,主要是因为这些天出了些小事。这个是用分支限界法求解单源最短路径问题的算法。
单源最短路径C语言实现,简单易懂,适合算法学习
/单源最短路径问题的Dijkstra算法 bool *s=new bool[maxint]; for(int i=1;i;i++) { dist[i]=c[v*n+i]; s[i]=false; if(dist[i]==maxint) prev[i]=0; else prev[i]=v; }
使用贪心算法实现单源点最短路径问题,C语言实现
使用Dijkstra算法求解单源最短路径问题,不仅求出最短路径,同时给出最短路径序列。