找到
2
篇与
最短路
相关的结果
-
C++求联通块数量 本文使用了下面五种方法求联通块数量： 并查集 深度优先搜索DFS 广度优先搜索BFS Floyd Kruskal #include<bits/stdc++.h> using namespace std; const int N = 110; const int M = 10010; int n, m; vector<int> g[N]; int ans = 0; // 1.并查集 int pre[N]; int find ( int x ) { return x == pre[x] ? pre[x] : pre[x] = find ( pre[x] ); } void merge ( int x, int y ) { int rx = find ( x ), ry = find ( y ); if ( rx != ry ) { pre[rx] = ry; } } void solveA() { for ( int i = 1; i <= n; i++ ) { pre[i] = i; } for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; g[u].emplace_back ( v ); g[v].emplace_back ( u ); merge ( u, v ); } for ( int i = 1; i <= n; i++ ) { if ( pre[i] == i ) { ans++; } } cout << ans; } // 2.深搜 int vis[N]; void dfs ( int x ) { for ( auto &u : g[x] ) { if ( vis[u] ) { continue; } vis[u] = true; dfs ( u ); } } void solveB() { for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; g[u].emplace_back ( v ); g[v].emplace_back ( u ); } for ( int i = 1; i <= n; i++ ) { if ( !vis[i] ) { dfs ( i ); ans++; } } cout << ans; } // 3.广搜 void bfs ( int x ) { queue<int> q; q.emplace ( x ); while ( !q.empty() ) { int u = q.front(); q.pop(); for ( auto &v : g[u] ) { if ( vis[v] ) { continue; } vis[v] = true; q.emplace ( v ); } } } void solveC() { for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; g[u].emplace_back ( v ); g[v].emplace_back ( u ); } for ( int i = 1; i <= n; i++ ) { if ( !vis[i] ) { bfs ( i ); ans++; } } cout << ans; } // 4.Floyd int adj[N][N]; void solveD() { for ( int i = 1; i <= n; i++ ) { adj[i][i] = 1; } for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; adj[u][v] = adj[v][u] = 1; } ans = 0; for ( int k = 1; k <= n; k++ ) { for ( int i = 1; i <= n; i++ ) { for ( int j = 1; j <= n; j++ ) { if ( adj[i][k] && adj[k][j] ) { adj[i][j] = 1; } } } } for ( int i = 1; i <= n; i++ ) { if ( !vis[i] ) { ans++; for ( int j = 1; j <= n; j++ ) { if ( adj[i][j] ) { vis[j] = true; } } } } cout << ans; } // 5.Kruskal 最小生成森林 struct Edge { int u, v; } e[M]; void solveE() { for ( int i = 1; i <= n; i++ ) { pre[i] = i; } for ( int i = 1; i <= m; i++ ) { int u, v; cin >> u >> v; e[i] = {u, v}; } ans = n; for ( int i = 1; i <= m; i++ ) { int u = e[i].u, v = e[i].v; int ru = find ( u ), rv = find ( v ); if ( ru != rv ) { merge ( ru, rv ); ans--; } } cout << ans; } // int main() { cin >> n >> m; // solveA(); // solveB(); // solveC(); // solveD(); solveE(); return 0; }
-
Dijkstra C++模板 邻接矩阵（无向图）模板 Dijkstra-邻接矩阵-堆优化.cpp // // Created by xiaoeyv on 2025/6/22. // #define maxn 2510 #define INF 0x3f3f3f3f #include <bits/stdc++.h> using namespace std; int n, m; int dis[maxn], vis[maxn]; int g[maxn][maxn]; int s; int main() { cin >> n >> m; memset(g, 0x3f, sizeof(g)); for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; // 无向图 g[u][v] = g[v][u] = min(g[u][v], w); } // cin >> s; s = 1; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[s] = 0; for (int i = 1; i <= n; i++) { int minn = INF, minp = -1; for (int j = 1; j <= n; j++) { if (!vis[j] && dis[j] < minn) { minn = dis[j]; minp = j; } } if (minp == -1) break; vis[minp] = 1; for (int j = 1; j <= n; j++) { if (g[minp][j] != INF) { dis[j] = min(dis[j], dis[minp] + g[minp][j]); } } } if (dis[n] == INF) cout << "INF"; else cout << dis[n]; }Dijkstra-邻接表-堆优化 // // Created by xiaoeyv on 2025/6/22. // #define maxn 2510 #define maxm 200010 #include<bits/stdc++.h> using namespace std; int n,m; int dis[maxn], vis[maxn]; vector<pair<int, int>> g[maxn]; int s; int main() { memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); cin>>n>>m; for(int i=0;i<m;i++) { int u,v,w; cin>>u>>v>>w; g[u].emplace_back(v,w); g[v].emplace_back(u,w); } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > pq; s = 1; dis[s] = 0; pq.emplace(0,s); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = 1; for (auto [v, w] : g[u]) { if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; pq.emplace(dis[v], v); } } } if (dis[n] == 0x3f3f3f3f) cout << "INF" << endl; else cout << dis[n] << endl; }Dijkstra-结构体-堆优化 // // Created by xiaoeyv on 2025/6/22. // #define maxn 2510 #define maxm 200010 #define INF 0x3f3f3f3f #include<bits/stdc++.h> using namespace std; int n, m; int dis[maxn], vis[maxn]; struct Edge { int to, w; }; vector<Edge> g[maxm]; int s; int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; // 无向图 g[u].push_back({v, w}); g[v].push_back({u, w}); } // cin >> s; s = 1; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[s] = 0; priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > q; q.emplace(0, s); while (!q.empty()) { int u = q.top().second; q.pop(); if (vis[u]) continue; vis[u] = 1; for (auto &e: g[u]) { int v = e.to, w = e.w; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; q.emplace(dis[v], v); } } } if (dis[n] == INF) cout << "INF"; else cout << dis[n]; }
