AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
clean
,
2021-02-04 16:36:54
,
所有人可见
,
阅读 233
C++ 代码
//保持清醒
#include<iostream>
#include<algorithm>
#include<cstring>
#include <climits> //INT_MAX
using namespace std;
int n,m;
const int N=510;
//三个数组都涉及到初始化问题
int g[N][N]; //邻接矩阵用于稠密图 10**5条边算稠密了
int dist[N]; //表示从一号点走到每个点的距离是多少
bool st[N]; //表示每个点的最短路是否已经确定
//一开始每个点到其它顶点的最短路都不确定,所以全为0。
//但你偏要钻牛角尖说1号顶点(源点)到1号顶点的最短距离是确定的
//那么你可以这样初始化st[]数组
//bool st[N]={0,1}; //0号下标的点为0还是1无所谓。1号下标的点(1号顶点)初始化为1。代表
//代表1号顶点已经在最短路集合s中
int dijkstra()
{
for(int i=1;i<=n;i++) //初始化dist[]数组
{
dist[i]=g[1][i]; //用1号顶点到其它顶点(1~n)之间的初始距离来初始化即可
} //很明显,dist[1][1]=0 如果其它距离后来有输入,那就是输入的值 否则就是无穷大
st[1]=true; //将源点加入最短路集合(st,s,p)。
int u;
for(int i=1;i<=n-1;i++)
{
int m_min=INT_MAX;
for(int j=1;j<=n;j++) //扫描一遍dist[]数组,找到离源点最近的点
{
if(!st[j]&&dist[j]<m_min) //一定要是不在最短路集合中的离源点最近的点
{
m_min=dist[j];
u=j; //记录这个离源点最近的顶点
}
}
st[u]=true; //将选出来的距离源点最近的顶点加入最短路径集合(s,st,p)中
for(int v=1;v<=n;v++) //寻找u所有的出边以用于更新其他顶点到源点的最短距离
{//这个不等于也可以写小于。一个意思
if(g[u][v]!=INT_MAX) //如果顶点与顶点v有边(u有出边)
{
if(dist[v]>dist[u]+g[u][v]) //原始>新增
{
dist[v]=dist[u]+g[u][v]; //更新
}
}
}
}
if(dist[n]==INT_MAX) return -1; //1号顶点和n号顶点不连通
return dist[n];
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i==j) g[i][j]=0;
else g[i][j]=INT_MAX; //图中涉及边长均不超过10000。NT_MAX是21亿
for(int i=1;i<=m;i++) //初始时,都无直达边,所以初始化为无穷大
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c); //在所有重边中选取一条最短的即可。不必理会自环
}
int t=dijkstra();
cout<<t<<endl;
return 0;
}