AcWing 850. Dijkstra求最短路 II
原题链接
简单
作者:
芝居気
,
2021-12-05 19:21:49
,
所有人可见
,
阅读 107
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<queue>
#include<cstring>
#include<cstdlib>
using namespace std;
#define db(x) cout<<#x<<" = "<<x<<" ";
typedef pair<int, int> PII;//到节点1 的距离
unordered_map<int, unordered_map<int,int>> mp;
//a 到b 的路径c
///(mp.f) -> (mp.s.f) len: mp.s.s
const int N = 200005;
bool st[N];//待确定布尔数组
int ans[N];
struct cmp {
bool operator ()(PII a, PII b) {
if (a.second != b.second)
return a.second > b.second;
else return a.first > b.first;
}
};
void add(int a, int b,int c)//又回到了用邻接矩阵建立图,哈希邻接矩阵无敌!!
{
if (mp[a][b] != 0)
{
mp[a][b] = min(mp[a][b], c);
return;
}
mp[a][b] = c;
}
void Dijkstra()
{
memset(ans, 0x3f, sizeof ans);
priority_queue<PII, vector<PII>, cmp> heap;
heap.push({ 1,0 });
st[1] = 0;
ans[1] = 0;
while (heap.size())
{
int temp = heap.top().first;
heap.pop();
if (st[temp]) continue;
st[temp] = 1;
//db(temp)
for (auto i : mp[temp])
{
int node = i.first, len = i.second;
//db(node) db(len) cout << endl;
if (ans[node] > ans[temp] + len)
{
ans[node] = ans[temp] + len;
heap.push({ node,ans[node] });
}
}
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int x, y,z;
cin >> x >> y >> z;
add(x, y, z);
}
Dijkstra();
if (ans[n] != 0x3f3f3f3f)
cout << ans[n];
else cout << -1;
}