最短路
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 25976 Accepted Submission(s): 11195
Problem Description
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的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条商店到赛场的路线。
输入保证至少存在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
思路:
最短路。Dijkstra。初始化距离全部为无穷大。邻接矩阵。
AC:
#include <stdio.h> #include <string.h> #define INF 9999999 int Map[105][105],vis[105]; int dis[105],n; void dijkstra(){ for(int i = 1;i <= n;i++){ int x,m = INF; for(int j = 1;j <= n;j++){ if(!vis[j] && m >= dis[j]){ m = dis[j]; x = j; } } vis[x] = 1; for(int j = 1;j <= n;j++){ if(dis[j] > dis[x] + Map[x][j]) dis[j] = dis[x] + Map[x][j]; } } } int main(){ int m; while(~scanf("%d%d",&n,&m) && (n + m)){ for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) Map[i][j] = INF; memset(vis,0,sizeof(vis)); for(int i = 1;i <= n;i++) dis[i] = (i == 1 ? 0 : INF); while(m--){ int a,b,c; scanf("%d%d%d",&a,&b,&c); Map[b][a] = c; Map[a][b] = c; } dijkstra(); printf("%d\n",dis[n]); } return 0; }
相关推荐
dijkstra算法的R语言实现。输入为邻接矩阵和权重矩阵。如果没有权重,则认为权重矩阵为邻接矩阵。输出为从源节点到网络其他节点的最短距离和最短路径。如果有多条最短路,可以选择同时输出多条路。
Dijkstra算法python实现,基于邻接矩阵及优先队列 不仅能够求解其实节点到各个节点的最短路径长度,而且并确定各条最短路径上的节点信息
基于matlab的dijkstra最短路由算法,可以分别通过邻接矩阵和坐标信息来计算。文件中JULI是通过各个点坐标及点之间连接情况进行判断,而JULI2则是根据邻接矩阵的信息来计算dijkstra最短路径。运行mian文件可以得到...
计算有向图的可达矩阵 两点间最短路的Dijkstra算法 关联矩阵和邻接矩阵相互转换 Floyd算法 Kruskal算法 Prim算法 求联通图最短距离矩阵 等
(1) 假设用带权的邻接矩阵a来表示带权有向图,a[i,j]表示弧,Vj>上的权值。若,Vj>不存在,则置a[I,j]为无穷大。S为已找到从V出发的最短路径的终点的集合,它的初始状态为空集。那么,从v0出发到图上其余各顶点(终点)...
MATLAB迪杰特斯拉源程序,用于在给出邻接矩阵求单元点点之间的距离
MATLAB中计算已知有向图、邻接矩阵情况下的最短路径
DIJKSTRA单源最短路径算法C/C++实现,内有注释,输入邻接矩阵,输入源点到终点最短路径长度。
1.2.1. 邻接矩阵 Adjacency matrix 1.2.2. 关联矩阵 Incidence matrix 1.2.3. 邻接表 Adjacency list 1.2.4. 弧表 Arc list 1.2.5. 星形表示 Star 1.3. 图的遍历 Traveling in graph 1.3.1. 深度优先搜索 Depth ...
1.2.1. 邻接矩阵 Adjacency matrix 1.2.2. 关联矩阵 Incidence matrix 1.2.3. 邻接表 Adjacency list 1.2.4. 弧表 Arc list 1.2.5. 星形表示 Star 1.3. 图的遍历 Traveling in graph 1.3.1. 深度优先搜索 Depth ...
| BELLMANFORD 单源最短路 O(VE) 4 | SPFA(SHORTEST PATH FASTER ALGORITHM) 4 | 第 K 短路(DIJKSTRA) 5 | 第 K 短路(A*) 5 | PRIM 求 MST 6 | 次小生成树 O(V^2) 6 | 最小生成森林问题(K 颗树)O(MLOGM). ...
1 字符串处理 5 1.1 KMP . . . . . . . . ....1.2 e-KMP ....1.3 Manacher ....1.4 AC 自动机 ....1.5 后缀数组 ....1.5.1 DA ....1.5.2 DC3 ....1.6 后缀自动机 ....1.6.1 基本函数 ....1.6.2 例题 ....1.7 字符串 hash ....2.1 素数 ....