Dijkstra C++模板

邻接矩阵（无向图）模板

Dijkstra-邻接矩阵-堆优化.cpp

//
// Created by xiaoeyv on 2025/6/22.
//

#define maxn 2510
#define INF 0x3f3f3f3f
#include <bits/stdc++.h>
using namespace std;

int n, m;
int dis[maxn], vis[maxn];
int g[maxn][maxn];
int s;

int main() {
    cin >> n >> m;

    memset(g, 0x3f, sizeof(g));

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        // 无向图
        g[u][v] = g[v][u] = min(g[u][v], w);
    }

    // cin >> s;
    s = 1;

    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;

    for (int i = 1; i <= n; i++) {
        int minn = INF, minp = -1;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && dis[j] < minn) {
                minn = dis[j];
                minp = j;
            }
        }
        if (minp == -1)
            break;
        vis[minp] = 1;
        for (int j = 1; j <= n; j++) {
            if (g[minp][j] != INF) {
                dis[j] = min(dis[j], dis[minp] + g[minp][j]);
            }
        }
    }

    if (dis[n] == INF)
        cout << "INF";
    else
        cout << dis[n];
}

Dijkstra-邻接表-堆优化

//
// Created by xiaoeyv on 2025/6/22.
//

#define maxn 2510
#define maxm 200010
#include<bits/stdc++.h>
using namespace std;

int n,m;
int dis[maxn], vis[maxn];
vector<pair<int, int>> g[maxn];
int s;

int main() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        g[u].emplace_back(v,w);
        g[v].emplace_back(u,w);
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > pq;
    s = 1;
    dis[s] = 0;
    pq.emplace(0,s);
    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = 1;
        for (auto [v, w] : g[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.emplace(dis[v], v);
            }
        }
    }
    if (dis[n] == 0x3f3f3f3f) cout << "INF" << endl;
    else cout << dis[n] << endl;
}

Dijkstra-结构体-堆优化

//
// Created by xiaoeyv on 2025/6/22.
//

#define maxn 2510
#define maxm 200010
#define INF 0x3f3f3f3f
#include<bits/stdc++.h>
using namespace std;

int n, m;
int dis[maxn], vis[maxn];

struct Edge {
    int to, w;
};

vector<Edge> g[maxm];
int s;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        // 无向图
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    // cin >> s;
    s = 1;

    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > q;
    q.emplace(0, s);

    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto &e: g[u]) {
            int v = e.to, w = e.w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.emplace(dis[v], v);
            }
        }
    }
    if (dis[n] == INF)
        cout << "INF";
    else
        cout << dis[n];
}