题目描述

要注意堆中的元素要把distance放在第一位，因为是要找距离最近的点，否则就要自己写仿函数

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e6 + 10;

typedef pair<int,int> PII;

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

int dist[N];
int n , m;

int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});
    while(!heap.empty()){
        auto iter = heap.top();
        heap.pop();
        int a = iter.second,distance = iter.first;
        if(st[a])continue;
        st[a] = true;
        for(int i = h[a];i != -1;i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[a] + w[i]){
                dist[j] = dist[a] + w[i];
                heap.push({dist[j] , j });
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

void insert(int a , int b ,int c){
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--){
        int a , b ,c;
        cin >> a >> b >> c;
        insert(a,b,c);
    }
    cout << dijkstra() << endl;
    return 0;
}