M表示边数，N表示点数

Dijkstra

堆优化O(MlogN)

const int N = 210, M = N * N;
int e[M], ne[M], h[N], idx;
long long w[M], d[N];
typedef pair<int, int> pii;
void add(int x, int y, int z){
    e[++idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx;
}
void dijkstra(){
    memset(d, 0x3f, sizeof d);
    priority_queue<pii> q;
    //len : 0, start : 0
    q.push({0, 0});
    d[0] = 0;
    while(q.size()){
        int x = q.top().second;
        q.pop();
        for(int i = h[x]; i; i = ne[i]){
            int y = e[i], z = w[i];
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
}

Spfa

O(MN)

const int N = 210, M = N * N;
int e[M], ne[M], h[N], idx;
long long w[M], d[N];
typedef pair<int, int> pii;
void add(int x, int y, int z){
    e[++idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx;
}
void Spfa(){
    memset(d, 0x3f, sizeof d);
    queue<int> q;
    bool vis[N];
    memset(vis, 0, sizeof vis);
    //start = 0;
    q.push(0);
    d[0] = 0;
    while(q.size()){
        auto x = q.front();
        q.pop();
        vis[x] = true;
        for(int i = h[x]; i; i = ne[i]){
            int y = e[i], z = w[i];
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                if(!vis[y]){
                    vis[y] = true;
                    q.push(y);
                }
            }
        }
    }
}

邻接矩阵适合存稠密图，邻接表适合存稀疏图

• 邻接矩阵 SC: O(N^2), TC: O(N^2)
• 邻接表 SC: O(M+N), TC: O(M)