今天加强了Kruskal算法，开始学习Dijkstra算法，开始复习bfs/dfs算法
#include <stdio.h>
#include <stdlib.h>int n, m, s, t;
int parent[20005];
typedef struct {int u, v, w;
} node;
node load[20005];int cmp(const void* a, const void* b)
{node* nodeA = (node*)a;node* nodeB = (node*)b;return nodeA->w - nodeB->w;
}int find(int x)
{if (parent[x] != x) parent[x] = find(parent[x]);return parent[x];
}void unionSet(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {parent[rootX] = rootY;}
}void Kru()
{int ans = 0;for (int i = 1; i <= n; i++) {parent[i] = i;}qsort(load, m, sizeof(node), cmp);for (int i = 0; i < m; i++){int x = load[i].u;int y = load[i].v;int w = load[i].w;if (find(x) != find(y)) {unionSet(x, y);ans = w;}if (find(s) == find(t)) break;}printf("%d", ans);
}int main()
{scanf("%d %d %d %d", &n, &m, &s, &t);for (int i = 0; i < m; i++)scanf("%d %d %d", &load[i].u, &load[i].v, &load[i].w);Kru();return 0;
}
#include <stdio.h>
#include <stdlib.h>#define MAX_N 1005
#define MAX_M 100005int n, m;
int f[MAX_N];typedef struct {int x, y, t;
} load;load loads[MAX_M];int cmp(const void* a, const void* b)
{load* loadA = (load*)a;load* loadB = (load*)b;return loadA->t - loadB->t;
}int find(int x)
{if (f[x] != x) f[x] = find(f[x]);return f[x];
}void unionSet(int x, int y)
{int rootX = find(x);int rootY = find(y);if (rootX != rootY)f[rootX] = rootY;
}int isAllConnected()
{int root = find(1);for (int i = 2; i <= n; i++) {if (find(i) != root){return 0;}}return 1;
}int main()
{scanf("%d %d", &n, &m);for (int i = 0; i < m; i++)scanf("%d %d %d", &loads[i].x, &loads[i].y, &loads[i].t);qsort(loads, m, sizeof(load), cmp);for (int i = 1; i <= n; i++)f[i] = i;int ans = -1;for (int i = 0; i < m; i++) {int x = loads[i].x;int y = loads[i].y;int t = loads[i].t;unionSet(x, y);if (isAllConnected()) {ans = t;break;}}printf("%d", ans);return 0;
} 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAXN 10005
#define MAXM 500005
#define INF 0x7fffffff// 边的结构体
typedef struct Edge {int to;int next;int weight;
} Edge;Edge edges[MAXM];
int head[MAXN];
int dist[MAXN];
int visited[MAXN];
int edgeCount = 0;// 添加边
void addEdge(int u, int v, int w) {edges[edgeCount].to = v;edges[edgeCount].weight = w;edges[edgeCount].next = head[u];head[u] = edgeCount++;
}// Dijkstra 算法
void dijkstra(int s, int n) {// 初始化距离数组为无穷大for (int i = 1; i <= n; i++) {dist[i] = INF;visited[i] = 0;}dist[s] = 0;for (int i = 1; i <= n; i++) {int minDist = INF, u = -1;// 找到距离源点最近且未访问的点for (int j = 1; j <= n; j++) {if (!visited[j] && dist[j] < minDist) {minDist = dist[j];u = j;}}if (u == -1) break;visited[u] = 1;// 更新与 u 相邻的点的距离for (int j = head[u]; j != -1; j = edges[j].next) {int v = edges[j].to;int w = edges[j].weight;if (!visited[v] && dist[u] + w < dist[v]) {dist[v] = dist[u] + w;}}}
}int main() {int n, m, s;scanf("%d %d %d", &n, &m, &s);// 初始化 head 数组memset(head, -1, sizeof(head));// 读取边的信息for (int i = 0; i < m; i++) {int u, v, w;scanf("%d %d %d", &u, &v, &w);addEdge(u, v, w);}// 执行 Dijkstra 算法dijkstra(s, n);// 输出结果for (int i = 1; i <= n; i++) {if (i > 1) printf(" ");printf("%d", dist[i] == INF? 0x7fffffff : dist[i]);}printf("\n");return 0;
}