找到
1
篇与
邻接表
相关的结果
-
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]; }
