AcWing 850. 纯STL通过,供参考
原题链接
简单
作者:
夏弦
,
2022-07-02 23:33:01
,
所有人可见
,
阅读 160
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<pair<int, int> >> graph(n+1); // <权重 到达的节点编号>
for (int i = 0; i < m; i++)
{
int x, y, v;
cin >> x >> y >> v;
graph[x].emplace_back(v, y);
}
priority_queue<PII, vector<PII>, greater<PII> > que;//从小到大
vector<int> dist(n + 1, 0x3f3f3f3f);//从点1到n的最小距离
que.emplace(0, 1);
dist[1] = 0;
while (!que.empty())
{
auto node = que.top().second;
if(que.top().first>dist[node])
{
que.pop();
continue;
}
dist[node] = min(que.top().first,dist[n]);
que.pop();
for (auto i : graph[node])
{
auto costNext = i.first;
auto nodeNext = i.second;
if (dist[nodeNext] > dist[node] + costNext)
{
dist[nodeNext] = dist[node] + costNext;
que.emplace(dist[nodeNext], nodeNext);
}
}
}
if (dist[n] < 1e9)
cout << dist[n] << endl;
else
cout << "-1" << endl;
return 0;
}