AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
西伯利亚的雪景
,
2021-05-22 19:52:25
,
所有人可见
,
阅读 287
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=505;
int n,m; //点数,边数
int p[N][N]; //稠密图用邻接矩阵存储
bool st[N]; //判断当前点是否已经找到最短路径,定义为全局变量默认值为false
int dist[N]; //当前点与起点的最短距离
int dijkstra(){ //迪杰斯特拉算法
memset(dist,0x3f,sizeof(dist));//初始化距离为正无穷
dist[1]=0; //初始化起点dist为0
for(int t=0;t<n;t++){
int minpoint =-1;
for(int i=1;i<=n;i++){//找到当前尚未确定最短距离的最小dist
if(st[i]==false&&(minpoint==-1||dist[i]<dist[minpoint]))
minpoint=i;
}
for(int j=1;j<=n;j++){//用新找到的最短距离更新所有点的最短距离
dist[j]=min(dist[j],dist[minpoint]+p[minpoint][j]);
}
st[minpoint]=true;//代表minpoint点已经找到了最短距离
}
if(dist[n]==0x3f3f3f3f) return -1;//若dist[n]为正无穷,则说明没有连接到该点的路径,则输出-1
return dist[n]; //否则输出dist[n]
}
int main(){
int a,b,c;
memset(p,0x3f,sizeof(p));//初始化邻接矩阵为正无穷
cin>>n>>m; //读入点数和边数
for(int t=0;t<m;t++){
cin>>a>>b>>c;
p[a][b]=min(p[a][b],c);//题目中可能存在重边,面对相同两个点之间的多条边,取最小的那条即可
}
cout<<dijkstra()<<endl;
return 0;
}