Dijkstra: 数组模拟链表

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII; // <距离-点编号>
#define fi first
#define se second
#define INF 0x3f3f3f3f

const int N=2e5;
int h[N], e[N], ne[N], w[N], idx; // 使用邻接表存储图
int DIS[N]; // 存储路径距离
bool vis[N]; // 存储访问状态
int n, m;

void ins(int x, int y, int wei){
    e[idx]=y;
    w[idx]=wei;
    ne[idx]=h[x];
    h[x]=idx++;
}


int dijkstra(){
    DIS[1]=0;
    priority_queue<PII, vector<PII>, greater<PII>> HEAP;
    HEAP.push({0, 1});

    while(!HEAP.empty()){
        int dist=HEAP.top().fi;
        int p=HEAP.top().se;
        HEAP.pop();
        if(!vis[p]){
            vis[p]=true;
            for(int i=h[p]; i!=-1; i=ne[i]){
                int pos=e[i];
                if(DIS[pos]>dist+w[i]){
                    DIS[pos]=dist+w[i];
                    HEAP.push({DIS[pos], pos});
                }
            }
        }
    }
    if(DIS[n]==INF) return -1;
    return DIS[n];
}


int main(){
    // 堆优化版的dijkstra算法
    memset(h, -1, sizeof h); // 初始化链表
    memset(DIS, 0x3f, sizeof DIS);
    cin>>n>>m;
    int x,y,w;
    while(m--){
        cin>>x>>y>>w;
        ins(x, y, w);
    }
    cout<<dijkstra()<<endl;
    return 0;
}

Dijkstra: vector存储图

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII; // <距离-点编号>
#define fi first
#define se second
#define INF 0x3f3f3f3f

const int N=2e5;
vector<PII> G[N];
int DIS[N]; // 存储路径距离
bool vis[N]; // 存储访问状态
int n, m;

int dijkstra(){
    DIS[1]=0;
    priority_queue<PII, vector<PII>, greater<PII>> HEAP; // 最小堆存储, 每次取出距离最短的边进行更新
    HEAP.push({0, 1});
    while(!HEAP.empty()){
        int dist=HEAP.top().fi;
        int node=HEAP.top().se;
        HEAP.pop();
        if(!vis[node]){
            for(auto &edge: G[node]){
                if(DIS[edge.fi]>dist+edge.se) {DIS[edge.fi]=dist+edge.se; HEAP.push({DIS[edge.fi], edge.fi});}
            }
            vis[node]=true;
        }
    }
    if(DIS[n]==INF) return -1;
    return DIS[n];
}



int main(){
    // 堆优化版的dijkstra算法
    memset(DIS, 0x3f, sizeof DIS);
    memset(vis, 0x00, sizeof vis);
    cin>>n>>m;
    int x,y,w;
    while(m--){
        cin>>x>>y>>w;
        G[x].push_back({y, w});
    }
    cout<<dijkstra()<<endl;
    return 0;
}