Dijkstra算法模板

使用数组存邻接表

代码块
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#ifdef ONLINE_JUDGE
#else
#define scanf scanf_s
#endif // ONLINE_JUDGE
#define FOR(i,a,b) for(int i = a;i <= b;i++)
#define ROF(i,a,b) for(int i = a;i >= b;i--)
ll read() {
    ll X = 0, w = 1; char c = getchar();
    while (c < '0' || c>'9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}
ll poww(ll a, ll b, ll mod) {
    ll base = 1;
    while (b) {
        if (b & 1) { base = base * a % mod; }
        b >>= 1; a = a * a % mod;
    }
    return base;
}
const int maxx = 10000 + 50;
int head, tail, n,m;
ll dis[maxx];
int matrix[maxx][maxx];
bool vis[maxx];
void init() {
    memset(matrix, 0x3f3f3f3f, sizeof matrix); 
    memset(dis, 0x3f3f3f3f, sizeof dis);
    FOR(i, 1, n) matrix[i][i] = 0;
    vis[head] = true; dis[head] = 0;
    int a, b,c;
    FOR(i,1,n) {
        a = read(), b = read(), c = read(); matrix[a][b] = matrix[b][a] = c;
    }
    FOR(i, 1, n) dis[i] = matrix[head][i];
}
int dijstrla() {
    int k = 1;
    while (k < m) {
        int minn = 0x3f3f3f3f, mini;
        FOR(i, 1, n) { 
            if (!vis[i] && dis[i] < minn) 
            { 
                minn = dis[i], mini = i; 
            } 
        }
        vis[mini] = 1, dis[mini] = minn;
        FOR(i, 1, n) {
            if (!vis[i]) { dis[i] = min(dis[i], dis[mini] + matrix[mini][i]); }
        }
        k++, minn = 0x3f3f33f;
    }
    return dis[tail];
}
int main() {
    m = read(), n = read(), head = read();//起始位head 共有m个点 n条边
    init(); dijstrla();
    int taill;
    while (tail = read()) { cout << dis[tail] << endl; }//输出起始点到tail的距离
}