堆优化版Dijkstra换板子
作者:
春江花月夜ovo
,
2024-03-26 23:10:07
,
所有人可见
,
阅读 8
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef pair<int, int> PII;
const int N = 150010;
vector<PII> edge[N];
vector<int> dist(N, 0x3f3f3f3f);
bool st[N];
int n, m;
void dijkstra()
{
priority_queue<PII, vector<PII>, greater<PII>> q;
dist[1] = 0;
q.push({0, 1});
while (!q.empty())
{
auto p = q.top(); q.pop();
int ver = p.second, val = p.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = 0; i < edge[ver].size(); i ++)
{
int j = edge[ver][i].second;
if (dist[j] > dist[ver] + edge[ver][i].first)
{
dist[j] = dist[ver] + edge[ver][i].first;
q.push({dist[j], j});
}
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i ++)
{
int a, b, c;
cin >> a >> b >> c;
edge[a].push_back({c, b});
}
dijkstra();
if (dist[n] > 0x3f3f3f3f / 2) cout << "-1\n";
else cout << dist[n] << "\n";
return 0;
}