AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
梨小畅
,
2021-05-20 22:09:29
,
所有人可见
,
阅读 274
题目分析
本题因为 边数m远大于点数n 所以采用邻接矩阵的表示方法 即使用朴素dijkstra算法
关于dijkstra:求有向带权图,a点到b点的最短距离
st[i]:标记i点是否被选过
g[i][j]:i点到j点的距离 (题目给)
dist[i]:i点到起点的最短距离 --> 求dist[n]
步骤如下:
1:初始化dist[i],令所有的点到起点的最短距离都为无穷大
2: dist[a]=0 --> 起点到起点的最短距离为0
3:在尚未加入集合st(没被st标记过)的点中 找到距离起点最近的点i(dist[i]在dist中最小)(第一次找到的是起点a)
4:此时dist[i] 已经确定,根据dist[i] 更新i点可以直接到达的点 的dist[]
5: 重复执行 步骤3和4 直到n个点距离起点的最短距离全部确定
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=510;
bool st[N]; // st[i] : 标记1点 到 i点的最短距离已经确定
int dist[N]; // dist[i]: 1点到i点的最短距离
int g[N][N]; // 稠密图 --> 邻接矩阵
int n,m;
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0; // 起点为1 ,起点到起点的最短距离 为0
for(int i=0;i<n;i++){ // 每次选1个点共n个点 所以需要进行n次
int t=-1;
// 选出还没有确定最短距离的点中 距离起点最近的点
for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
st[t]=true; // 标记 ,说明t被选中
//根据dist[t] 更新t点可以直接走向的点 其距起点的最短距离
for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+g[t][j]);
}
// 循环结束后 最后得到的dist[i] 才是起点到 i点的最短距离 ,循环进行中得到的只是个暂定值
if(dist[n]==0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
memset(g,0x3f,sizeof g);
cin>>n>>m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
cout<<dijkstra()<<endl;
return 0;
}