算法板子

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5e4 + 10;
int he[N], ne[N], ver[N], edge[N], tot;
priority_queue<pair<int, int>> q;
int d[N], n, m;
bool v[N];
void insert(int x, int y, int z) {
    ver[++tot] = y;
    edge[tot] = z;
    ne[tot] = he[x];
    he[x] = tot;
};
void dijkstra() {
    memset(d, 0x3f, sizeof d);
    memset(v, false, sizeof v);
    d[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto pa = q.top(); q.pop();
        int x = pa.second;
        if (v[x]) continue;
        v[x] = true;
        for (int i = he[x]; i; i = ne[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
};
int main() {
    cin >> n >> m;
    tot = 0;
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        insert(x, y, z);
    }
    dijkstra();
    if (d[n] == 0x3f3f3f3f) {
        cout << - 1 << endl;
    } else {
        cout << d[n] << endl;
    }
    return 0;
};
本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/dijkstra-heap/
最后修改日期:2020年6月18日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。