两种写法均为堆优化版本的

写法一

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define fast ios ::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using ll = long long;
typedef pair<int, int> PII;
#define OUT(v)                         \
    for (int k = 0; k < v.size(); ++k) \
        cout << v[k] << ' ';           \
    cout << endl;
const int N = 3e6 + 10;
int h[N], e[2 * N], ne[N];
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
ll mul(ll x, ll y) {return (1LL * x * y) % mod; }
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int Dx[] = {0, -1, 0, 1, 1, -1, -1, 1}, Dy[] = {-1, 0, 1, 0, 1, -1, 1, -1};




void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<PII> > g(n + 1);
    vector<int> md(n + 1, inf);
    vector<bool> fi(n + 1, false);
    priority_queue<PII, vector<PII>, greater<PII> > q;
    while(m--) {
        int s, e, v;
        cin >> s >> e >> v;
        g[s].push_back({e, v});
    }
    md[1] = 0;
    //q.push({0, 1});
    for (int i = 1; i <= n; i++) {
        int minval = inf, cur = 1;

        while(!q.empty() && fi[q.top().second]) q.pop();
        if (!q.empty()) {
            minval = q.top().first;
            cur = q.top().second;
        }
        // 更新cur能到达的节点
        int len = g[cur].size();
        for (int j = 0; j < len; j++) {
            int val = g[cur][j].second;
            int v = g[cur][j].first;
            if (!fi[v]) {
                md[v] = min(md[v], md[cur] + val);
            }
            q.push({md[v], v});
        }
        //标记cur为结束
        fi[cur] = true;
    }
    //OUT(md);
    if (md[n] != inf) cout << md[n];
    else cout << -1;

}


int main() {
    solve();
    return 0;
}

法二

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define fast ios ::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using ll = long long;
typedef pair<int, int> PII;
#define OUT(v)                         \
    for (int k = 0; k < v.size(); ++k) \
        cout << v[k] << ' ';           \
    cout << endl;
const int N = 3e6 + 10;
int h[N], e[2 * N], ne[N];
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
ll mul(ll x, ll y) {return (1LL * x * y) % mod; }
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int Dx[] = {0, -1, 0, 1, 1, -1, -1, 1}, Dy[] = {-1, 0, 1, 0, 1, -1, 1, -1};




void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<PII> > g(n + 1);
    vector<int> md(n + 1, inf);
    vector<bool> fi(n + 1, false);
    priority_queue<PII, vector<PII>, greater<PII> > q;
    while(m--) {
        int s, e, v;
        cin >> s >> e >> v;
        g[s].push_back({v, e});
    }
    md[1] = 0;
    q.push({0, 1});

    while(!q.empty()) {
        int minval = q.top().first;
        int cur = q.top().second;
        q.pop();
        if (fi[cur]) continue;
        int len = g[cur].size();
        for (int j = 0; j < len; j++) {
            int vi = g[cur][j].second;
            int val = g[cur][j].first;
            if (!fi[vi] && md[vi] > md[cur] + val) {
                md[vi] = md[cur] + val;
                q.push({md[vi], vi});
            }
        }
        fi[cur] = true;
    }

    //OUT(md);
    if (md[n] != inf) cout << md[n];
    else cout << -1;

}


int main() {
    solve();
    return 0;
}