Acwing 849. Dijkstra求最短路 I

链接:849. Dijkstra求最短路 I - AcWing题库

/*题解:dijkstra算法模板对于单源最短路径dijkstra1.每次找到当前距离源最近的节点 作为确定距离的点2.通过这个点看能否让其他的节点来松弛其他点到源的距离重复12操作*/
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;const int N = 5e2+100;
const int inf = 0x3f3f3f3f;
int g[N][N];
int dist[N];
int st[N];
int n,m;void dijkstra(){memset(dist,0x3f,sizeof dist);memset(st,0,sizeof st);dist[1]=0;for(int i=0;i<n-1;i++){int t = -1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dist[t]>dist[j])){//找到当前距离1最近的节点作为确定的节点 t=j;}}st[t] = 1;for(int j =1;j<=n;j++){//用最新确定的节点来松弛其他的点和源的距离// if(st[j]){dist[j] = min(dist[j],dist[t]+g[t][j]);// }}}if(dist[n]==inf){cout<<-1<<endl;}else cout<<dist[n]<<endl;// cout<<dist[n]<<endl;}int main(){cin>>n>>m;memset(g,0x3f,sizeof g);while(m--){int a,b,c;cin>>a>>b>>c;g[a][b] = min(g[a][b],c);}dijkstra();return 0;
}