Floyd

#include <cstdio>
待補(bǔ)坑

Dijkstra

樸素o(n^2)

int n, m;// 點(diǎn)數(shù)量以及邊數(shù)量
int w[MAXN][MAXN];// 記錄任意兩點(diǎn)之間距離
int d[MAXN];// 點(diǎn)的權(quán)值
int v[MAXN];// 標(biāo)記數(shù)組
void Dijkstra() {
    // 初始化所有點(diǎn)權(quán)為INF
    for(int i=2; i<=n; i++) d[i] = INF;

    for(int i=1; i<=n; i++) {
        int x, m = INF;
        // 選出相連的d值最小的點(diǎn)
        for(int y=1; y<=n; y++) if(!v[y] && d[y]<=m) m = d[x=y];
        // 標(biāo)記此點(diǎn)為已訪問(wèn)
        v[x] = true;
        // 更新最小d值
        for(int y=1; y<=n; y++) {d[y] = min(d[y], d[x] + w[x][y]);}

    }
}