#include <stdio.h>int main(){int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min;int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值//读入n和m,n表示顶点个数,m表示边的条数scanf("%d %d",&n,&m);//初始化for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j) e[i][j]=0; else e[i][j]=inf;//读入边for(i=1;i<=m;i++){scanf("%d %d %d",&t1,&t2,&t3);e[t1][t2]=t3;}//初始化dis数组,这里是1号顶点到其余各个顶点的初始路程for(i=1;i<=n;i++)dis[i]=e[1][i];//book数组初始化for(i=1;i<=n;i++)book[i]=0;book[1]=1;//Dijkstra算法核心语句for(i=1;i<=n-1;i++){//找到离1号顶点最近的顶点min=inf;for(j=1;j<=n;j++){if(book[j]==0 && dis[j]<min){min=dis[j];u=j;}}book[u]=1;for(v=1;v<=n;v++){if(e[u][v]<inf){if(dis[v]>dis[u]+e[u][v])dis[v]=dis[u]+e[u][v];}} }//输出最终的结果for(i=1;i<=n;i++)printf("%d ",dis[i]);getchar();getchar();return 0;}
详细解决方案
最短路之dijkstra
热度:62 发布时间:2024-01-14 21:56:04.0
相关解决方案
- NYOJ - 115 - 城市平乱 ( 最短路 Dijkstra )
- hdu 2112 HDU Today(dijkstra)
- HDOJ 2066 一个人的旅行(dijkstra)
- HDOJ 1596 find the safest road(floyd +dijkstra 两种方法)
- hduoj 2544 最短路(模板 dijkstra + floyd )
- (Dijkstra)L2-001 紧急救援 (25 分)
- (Dijkstra)7-13 天梯地图 (30 分)
- (差分约束,Dijkstra+堆优化)poj3159 Candies
- ( 最短路 Dijkstra ) NYOJ - 115 - 城市平乱
- P4011 孤岛营救问题,状态压缩+dijkstra。
- HDU Today Dijkstra 最短路径
- 最短路径问题 最短路径 dijkstra
- 最短路模板[spfa][dijkstra+堆优化][floyd]
- POJ - 2253 Frogger 【dijkstra】
- HDU - 2544 最短路【dijkstra】
- 最短算法 Dijkstra
- L3-005 垃圾箱分布 (30 分)(dijkstra)
- L2-001 紧急救援 (25 分)(dijkstra)
- A - MPI Maelstrom POJ - 1502(dijkstra 板子题 可以不用优化的,但是我还是用优先队列优化)
- L2-001 紧急救援 (25 分) (dijkstra)
- 7-2 公路村村通 迪杰斯特拉(dijkstra)算法
- 路径(蓝桥杯+Dijkstra)
- 租用游艇 dijkstra
- Dijkstra-基础
- Dijkstra--延申
- Dijkstra 最短路径算法的一种高效率实现
- POJ 2253 Frogger(Dijkstra or Floyd)
- HDU 1874 通畅工程续(Dijkstra)
- 最短路 Dijkstra HDU-2544
- [算法] poj 2387 单源最短路 Dijkstra