AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
YMYS
,
2024-04-09 21:22:39
,
所有人可见
,
阅读 16
轻轻松松
//
//
//
#pragma GCC target ("avx")
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
using namespace __gnu_cxx;
using ll = long long;
typedef pair<int, int> PII;
const int N = 510;
int n,m;
int a[N][N];//邻接矩阵
bool st[N];
int d[N];//存最短路径
int Dijkstra(){
memset(d, 0x3f, sizeof d);
d[1] = 0;
for(int i=0;i<n;i++){
int t = -1;
for(int j=1;j<=n;j++){
if(!st[j] && (t == -1 || d[t] > d[j])){
t = j;
}
}
st[t] = true;//标记为已经是最短路径
for(int j = 1;j<=n;j++){
d[j] = min(d[j], d[t] + a[t][j]);
}
}
if(d[n] == INF) return -1;
return d[n];
}
signed main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
memset(a,0x3f, sizeof a);
cin>>n>>m;
while (m--)
{
int aa,b,c;
cin>>aa>>b>>c;
a[aa][b] = min(a[aa][b], c);//防止重边
}
cout<<Dijkstra()<<endl;
return 0;
}