问题标题: 暑假部分代码模版（图和最短路径算法）（2023.7）

Floyd
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        }
    }
}

Dijkstra
int n, m;
bool found[MAXN];
int dis[MAXN]
struct edge {
    int next;
    int w;
};
vector<edge> g[MAXN];
void Dijkstra(int st) {
    memset(found, false, sizeof(found));
    memset(dis, 0x3f, sizeof(dis));
    dis[st] = 0;
    while (1) {
        int u = -1;
        for (int i = 1; i <= n; i++) {
            if (!found[i] && (u == -1 || dis[i] < dis[u]))  u = i;
        }
        if (u == -1) break;
        found[u] = true;
        for (int i = 0; i < g[u].size(); i++) {
            edge e = g[u][i];
            if (!found[e.next]) dis[e.next] = min(dis[e.next], dis[u] + e.w);
        }
    }
    return ;
}

Prim
int MST_prim() {
    int ans = 0;
    memset(dis, 0x3f, sizeof(dis));
    memset(found, false, sizeof(found));
    dis[1] = 0;
    while (1) {
        int u = -1;
        for (int i = 0; i <= n; i++) {
            if (!found[i] && (u == -1 || dis[i] < dis[u])) {
                u = i;
            }
        }
        if (u == -1) break;
        found[u] = true;
        ans += dis[u];
        for (int i = 0; i <= n; i++) {
            if (!found[i] && g[u][i] < dis[i]) {
                dis[i] = g[u][i];
            }
        }
    }
    return ans;
}

拓扑排序
int n, m;
vector<int> g[MAXN];
queue<int> q;
int f[MAXN], in[MAXN];

void Topsort() {
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int t = q.front();
        cout << t << " ";
        q.pop();
        for (int i = 0; i < g[t].size(); i++) {
            int idx = g[t][i];
            if (--in[idx] == 0) {
                q.push(idx);
            }
        }
    }
}