- 浏览: 583732 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
题(HDU2544):
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?
Input
输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。
接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
源码:
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?
Input
输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。
接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。
Output
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间
Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
Sample Output
3
2
import java.util.Scanner; import java.util.Queue; import java.util.LinkedList; public class Main{ static final int INF = 99999999; private int map[][];//邻接矩阵 private int dist[];//最终存放从商店到各路口的最短距离 private boolean visit[];//visit[i]标记dist[i]是否已经求出。 private int n;//路口和道路数(顶点和边数) public Main(int n,int[][] map){ this.n=n; this.map=map; dist=new int[n+1]; } private void floyd(){ //Floyd算法 for(int k = 1; k <= n; k++) //k为中间点 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(map[i][k] + map[k][j] < map[i][j]){ map[i][j] = map[i][k] + map[k][j]; } System.out.println(map[1][n]); } private void dijk() { //Dijkstra算法 int next=0, MIN; visit=new boolean[n+1]; for(int i =1; i <= n; i++) dist[i] = INF; dist[1] = 0; for(int i = 1; i <= n; i++) { MIN = INF; for(int j = 1; j <= n; j++) if(!visit[j] && dist[j] <= MIN){ MIN = dist[j]; next=j; } if(MIN == INF) break; visit[next] = true; for(int j = 1; j <= n; j++) if(!visit[j] && dist[j] > dist[next] + map[next][j]) dist[j] = dist[next] + map[next][j]; } System.out.println(dist[n]); } private void spfa(){ //SPFA算法 int now; visit=new boolean[n+1]; for(int i = 1; i <= n; i++) dist[i] = INF; dist[1] = 0; Queue<Integer> Q=new LinkedList<Integer>(); Q.offer(1); visit[1] = true; while(!Q.isEmpty()){ now = Q.poll(); visit[now] = false; for(int i = 1; i <= n; i++){ if(dist[i] > dist[now] + map[now][i]){ dist[i] = dist[now] + map[now][i]; if(visit[i] == false) { Q.offer(i); visit[i] = true; } } } } System.out.println(dist[n]); } public static void main(String[] args){ Scanner in=new Scanner(System.in); while(in.hasNext()) { int n=in.nextInt();//图的顶点数 int m=in.nextInt();//边数 if(n==0&&m==0) break; int[][] map=new int[n+1][n+1]; for(int i = 1; i <= n; i++){//初始化 for(int j = 1; j <= n; j++){ if(i == j) map[i][j] = 0; else{ map[i][j] = map[j][i] = INF; } } } int vi, vj, cost; while(m-->0){//m条边的数据 vi=in.nextInt(); vj=in.nextInt(); cost=in.nextInt(); if(cost < map[vi][vj]){ map[vi][vj] = map[vj][vi] = cost; } } Main ma=new Main(n,map); // ma.floyd(); // ma.dijk(); ma.spfa(); } } }
源码:
- hdu2544.zip (1.1 KB)
- 下载次数: 13
发表评论
-
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1525POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
图的练习题(有解答)
2012-12-27 22:23 26111. 填空题 ⑴ 设无向图G ... -
邻接表实现图的广搜和深搜(java模板)
2012-12-11 17:04 2404//邻接表实现图的广搜和深搜(java模板) impor ... -
邻接矩阵实现图的广搜和深搜(java模板)
2012-12-10 20:37 1838经常要用到,放到这里备用!! //邻接矩阵实现图的广搜和深搜 ... -
如何求无向图的最小环
2012-11-13 19:02 2740POJ1734 题意:给定一个N个点的无向图,求一个最小环(各 ... -
深度优先搜索输出有向图中的所有环(JAVA)
2012-11-06 14:22 9549如图:求出有向图的所有环。 import java.uti ... -
Dijkstra算法解HDU1874
2012-11-05 10:15 1300Dijkstra算法是用来解 ... -
SPFA算法求单源最短路径
2012-11-04 23:00 1864很多时候,给定的图存在负权边,这时类似Dijkstra等算法 ... -
图解Bellman-Ford算法
2012-11-03 19:39 5818Bellman-Ford算法: ... -
Bellman-Ford算法教学PPT
2012-11-03 12:06 1398Dijkstra算法是处理单源最短路径的有效算法,但它 ... -
昆虫的同性恋
2012-11-01 19:21 1352题目大意: 输入一个数t,表示测试组数。然后每组第一行两 ... -
拓扑排序入门练习
2012-11-01 16:51 1531拓扑排序简单来说 ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3984一、什么是并查集 ... -
无前趋的顶点优先的拓扑排序方法(JAVA)
2012-10-28 20:20 1783无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输 ... -
Kruskal算法和prim算法求最小生成树学习小结(JAVA)
2012-10-26 14:02 4963prim算法是用来实现图最小生成树的2种常用方法之一,P ... -
图的邻接表存储及遍历(JAVA)
2012-10-10 10:58 5354为图的每个顶点所发出的边建立一个单链表,用一顶点数组存储 ... -
弗洛伊德(Floyd)算法求任意两点间的最短路径
2012-10-01 07:46 6219Floyd-Warshall算法(Floyd-Warsha ... -
单源最短路径( Dijkstra算法)JAVA实现
2012-09-14 14:30 9033单源最短路径问题,即在图中求出给定顶点到其它任一顶 ... -
深度优先搜索与有向无环图的拓扑排序(java实现)
2012-09-11 13:05 5467当每个任务有前后置关系时,需要找到一种满足前后置关系的路 ... -
最小生成树:Kruskal(克鲁斯卡尔)算法实现(java)
2012-09-01 20:50 2591算法描述:Kruskal(克鲁斯卡尔)算法需要对图的边进行访问 ...
相关推荐
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
对同一场景分别进行dijkstra算法求指定节点间的最短路径,floyd求任意端间最短路径。 报告中含C++代码
求最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
Dijkstra和Floyd算法找最短路径matlab实现,通信网作业
floyd算法,求最短路径的权值,java实现的
最短路径算法 floyd
讲了常用的求单源最短路径的算法,非常好的资料。。
NULL 博文链接:https://128kj.iteye.com/blog/1689015
floyd计算最短路径,只需要更改邻接矩阵
使用floyd warshall算法求图中任意两点间最短路径 graph shortest path
Floyd算法是经典的最短路径算法之一,应用广泛,可以求解多对多和一对一的最短路;
Floyd-Warshall算法是一种计算图中所有顶点对之间的最短路径的动态规划算法。其基本思想是通过逐步考虑所有顶点作为中间点来更新最短路径。ISOMAP(Isometric Mapping)是一种非线性降维方法,它使用最短路径距离来...
在单个Julia文件 中的图中 实现 Dijkstra 和 Warshall-Floyd 最短路径算法
用C++ 语言编写 用Floyd算法求有向图中任意两点间的最短路径 由用户输入顶点和有向边的信息
最短路径floyd算法实现最短路径floyd算法实现最短路径floyd算法实现最短路径floyd算法实现
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。采用C++实现
Floyd最短路径算法的java实现,文件内附测试用例拓扑。
构造邻接矩阵,利用Floyd算法求最短路径。课程设计~~~
该程序是我写的博客“一起talk C栗子吧(第五十五回:C语言实例--图的最短路径三)”的配套程序,共享给大家使用