Dijkstra 最短路

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n'
#define mem(z, o) memset(z, o, sizeof(z))
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define fr(l, ft, ed) for (int l = (ft); l <= (ed); ++l)

const int N = 1e6+10;
// ---------------------------- 堆优化 O(m log n)------------------------

int h[N], e[N], ne[N], idx, w[N];
int vis[N], n, dist[N];
using pii = pair<int, int>;
inline void add(int u, int v, int ww)
{ 
    e[idx] = v, w[idx] = ww, ne[idx] = h[u], h[u] = idx++; 
}
struct cmp{  // 重写仿函数
    bool operator() (const pii &A, const pii &B) const
    {
        return A.first > B.first;
    }
};
int Dijkstra(int u)
{
    mem(dist, 0x3f);
    dist[u] = 0;
    priority_queue<pii, vector<pii>, cmp>heap;
    heap.push({0, 1});
    while (!heap.empty())
    {
        auto t = heap.top(); heap.pop();
        int dd = t.first, id = t.second;

        if (vis[id]) continue;
        vis[id] = 1;

        for (int i = h[id]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dd + w[i])
            {
                dist[j] = dd + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
signed main()
{
    IOS
    int m; cin >> n >> m;
    mem(h, -1);
    while (m--)
    {
        int a, b, ww; cin >> a >> b >> ww;
        add(a, b, ww);
    }
    cout << Dijkstra(1) << endl;
    return 0;
}

-------------------- 朴素 O(n ^ 2 + m)------------------

// int g[510][510], n;
// int vis[510], dist[510];
// int Dijkstra(int u)
// {
//     mem(dist, 0x3f);
//     dist[u] = 0;
//     for (int i = 0; i < n; ++i)
//     {
//           在还未确定最短路的点中，寻找距离最小的点
//         int t = -1;
//         for (int j = 1; j <= n; ++j)
//             if (!vis[j] && (t == -1 || dist[t] > dist[j]))
//                 t = j;
         // 用t更新其他点的距离
//         for (int j = 1; j <= n; ++j)
//             dist[j] = min(dist[j], dist[t] + g[t][j]);
//         vis[t] = 1;
//     }

//     if (dist[n] == 0x3f3f3f3f) return -1;
//     return dist[n];
// }