update 2023/9/29：更改 Prim 算法的遗漏点

最小生成树

题目：P3366 【模板】最小生成树

$\mathcal {Kruskal}$

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n, m, ans, cnt;
int fa[N];
struct node {
	int x, y, len;
}e[N];
bool cmp(node a, node b) {
	return a.len < b.len;
}

int dfs(int x) {
//	return fa[x] == x ? x : dfs(fa[x]);
	if (fa[x] == x) {
		return x;
	}
	fa[x] = dfs(fa[x]);
	return fa[x];
}

bool init() {
	for (int i = 1; i <= m; i++) {
		fa[i] = i;
	}
}

void kruskal() {
	for (int i = 1; i <= m; i++) {
		int fx = dfs(e[i].x);
		int fy = dfs(e[i].y);
		if (fx != fy) {
			fa[fx] = fy;
			ans += e[i].len;
			cnt++;
		}
	}
}

int main() {
    cin >> n >> m;
    init();
    for (int i = 1; i <= m; i++) {
    	scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].len);
	}
	sort(e+1, e+m+1, cmp);
	kruskal();
	if (cnt == n-1) {
		cout << ans;
	} else {
		cout << "orz";
	}
    return 0;
}

$\mathcal{Prim}$

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 5010;
int G[N][N], vis[N], dis[N];

void init() {
	memset(G, INF, sizeof(G));
	memset(dis, INF, sizeof(dis));
}

void prim(int n) {
	dis[1] = 0;
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		int mi = INF;
		int id = -1;
		for (int j = 1; j <= n; j++) {
			if (vis[j] == 0 && dis[j] < mi) {
				mi = dis[j];
				id = j;
			}
		}
		if (id == -1) {
			printf("orz\n");
			return;
		}
		ret += mi;
		vis[id] = 1;
		for (int j = 1; j <= n; j++) {
			if (vis[j] == 0 && G[id][j] < dis[j]) {
				dis[j] = G[id][j];
			}
		}
	}
	cout << ret;
}

int main() {
	init();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
    	int x, y, z;
    	cin >> x >> y >> z;
    	if (z < G[x][y]) {
    		G[x][y] = G[y][x] = z;
		}
	}
	prim(n);
    return 0;
}

最短路径

单源最短路模板（无题目）

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 5010;
int G[N][N], vis[N], dis[N];

void init() {
	memset(G, INF, sizeof(G));
	memset(dis, INF, sizeof(dis));
}

void dijkstra(int n) {
	dis[1] = 0;
	int ret = 0;
	for (int i = 1; i <= n; i++) {
		int mi = INF;
		int id = -1;
		for (int j = 1; j <= n; j++) {
			if (vis[j] == 0 && dis[j] < mi) {
				mi = dis[j];
				id = j;
			}
		}
		vis[id] = 1;
		for (int j = 1; j <= n; j++) {
			if (dis[id] + G[id][j] < dis[j]) {
				dis[j] = dis[id] + G[id][j];
			}
		}
	}
	cout << dis[n];
}

int main() {
	init();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
    	int x, y, z;
    	cin >> x >> y >> z;
    	if (z < G[x][y]) {
    		G[x][y] = G[y][x] = z;
		}
	}
	dijkstra(n);
    return 0;
}

$\mathbf{Dijkstra }$ (普通版)

P3371 【模板】单源最短路径（弱化版）

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 定义边的结构体
struct Edge {
    int to;
    int weight;
};

// SPFA算法求解最短路径
vector<int> spfa(int n, int m, int s, const vector<vector<Edge>>& graph) {
    // 初始化距离数组，默认为无穷大
    vector<int> distance(n + 1, INT_MAX);
    vector<bool> inQueue(n + 1, false);  // 记录节点是否在队列中

    // 使用队列保存需要进行松弛操作的节点
    queue<int> q;

    // 起始点入队列
    q.push(s);
    distance[s] = 0;
    inQueue[s] = true;

    // SPFA算法迭代
    while (!q.empty()) {
        int currNode = q.front();
        q.pop();
        inQueue[currNode] = false;

        // 遍历当前节点的邻居节点
        for (const Edge& edge : graph[currNode]) {
            int nextNode = edge.to;
            int nextDistance = distance[currNode] + edge.weight;

            // 如果新的距离更小，则更新距离数组并将节点加入队列
            if (nextDistance < distance[nextNode]) {
                distance[nextNode] = nextDistance;
                if (!inQueue[nextNode]) {
                    q.push(nextNode);
                    inQueue[nextNode] = true;
                }
            }
        }
    }

    return distance;
}

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

    // 初始化图的邻接表
    vector<vector<Edge>> graph(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // 添加边到邻接表中
        graph[u].push_back({v, w});
    }

    // 调用SPFA算法求解最短路径
    vector<int> shortestPaths = spfa(n, m, s, graph);

    // 输出最短路径长度
    for (int i = 1; i <= n; ++i) {
        if (shortestPaths[i] == INT_MAX) {
            cout << "2147483647 ";  // 表示不可达
        } else {
            cout << shortestPaths[i] << " ";
        }
    }
    cout << endl;

    return 0;
}

$\mathbf{Dijkstra }$ (堆优化）

P4779 【模板】单源最短路径（标准版）

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

// 定义边的结构体
struct Edge {
    int to;
    int weight;
};

// 使用邻接表存储图
vector<vector<Edge>> graph;

// Dijkstra算法求解最短路径
vector<int> dijkstra(int n, int m, int s) {
    // 初始化距离数组，默认为无穷大
    vector<int> distance(n + 1, INT_MAX);

    // 定义优先队列（最小堆），保存节点和当前距离
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    // 将起始点放入队列中
    pq.push(make_pair(0, s));
    distance[s] = 0;

    // 开始迭代
    while (!pq.empty()) {
        // 取出队列中距离最小的节点
        int currNode = pq.top().second;
        int currDistance = pq.top().first;
        pq.pop();

        // 如果当前距离大于已知最短路径，则继续下一个节点
        if (currDistance > distance[currNode]) continue;

        // 遍历当前节点的所有邻居节点
        for (const Edge& edge : graph[currNode]) {
            int nextNode = edge.to;
            int nextDistance = currDistance + edge.weight;

            // 如果新的距离更小，则更新距离数组并将节点放入队列中
            if (nextDistance < distance[nextNode]) {
                distance[nextNode] = nextDistance;
                pq.push(make_pair(nextDistance, nextNode));
            }
        }
    }

    return distance;
}

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

    // 初始化图的邻接表
    graph.resize(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // 添加边到邻接表中
        graph[u].push_back({v, w});
    }

    // 调用Dijkstra算法求解最短路径
    vector<int> shortestPaths = dijkstra(n, m, s);

    // 输出最短路径长度
    for (int i = 1; i <= n; ++i) {
        if (shortestPaths[i] == INT_MAX) {
            cout << "2147483647 ";  // 表示不可达
        } else {
            cout << shortestPaths[i] << " ";
        }
    }
    cout << endl;

    return 0;
}