用优先队列进行优化 朴素dijkstra

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;
const int  N = 1e6 + 10;
typedef pair<int, int> PII;

int h[N], e[N], ne[N], w[N], idx;
int dist[N], n, m;
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a]; w[idx] = c, h[a] = idx ++;
}
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist)
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int x = t.second, distance = t.first;

        if(st[x]) continue;
        st[x] = true;

        for(int i = h[x]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[x] + w[i])
            {
                dist[j] = dist[x] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}



int main()
{
    memset(h, -1, sizeof h);

    cin.tie(0);
    cin >> n >> m;
    int a, b, c;

    while(m--)
    {
        cin >> a >> b >> c;

        add(a, b, c);
    }

    int t = dijkstra();
    cout << t;
}