AcWing 849. Dijkstra求最短路 I
原题链接
简单
#include <bits/stdc++.h>
using namespace std;
const int N = 510 , M = 1e5+10 , INF = 0x3f3f3f3f;
int n , m;
struct edge{
int to , w;
};
struct node{
int id , dis;
bool operator < (const node &u) const{return dis > u.dis;};
};
vector <edge> g[N];
int d[N];
bool vis[N];
void Dijkstra(int s)
{
//init
memset(d , INF , sizeof(d));
d[s] = 0;
priority_queue<node> q;
q.push({s , d[s]});
while(!q.empty())
{
node t = q.top();
q.pop();
if(vis[t.id]) continue;
vis[t.id] = true;
for(int i = 0; i < g[t.id].size() ; i++)
{
edge e = g[t.id][i];
if(vis[e.to]) continue;
if(d[e.to] > d[t.id] + e.w)
{
d[e.to] = d[t.id] + e.w;
q.push({e.to , d[e.to]});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
int u , v , w; cin >> u >> v >> w;
g[u].push_back({v , w});
}
Dijkstra(1);
if(d[n] !=INF) cout << d[n] ;
else cout << -1;
return 0;
}