fsfs
2025-06-01 18:36:28
发布于：浙江
2阅读
0回复
0点赞
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> ii;
int main() {
int n, m;
cin >> n >> m;
vector<vector<ii>> adj(n + 1);
vector<vector<int>> minWeight(n + 1, vector<int>(n + 1, INT_MAX));
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
if (w < minWeight[u][v]) {
minWeight[u][v] = w;
}
if (w < minWeight[v][u]) {
minWeight[v][u] = w;
}
}
for (int u = 1; u <= n; ++u) {
for (int v = 1; v <= n; ++v) {
if (minWeight[u][v] != INT_MAX) {
adj[u].push_back({v, minWeight[u][v]});
}
}
}
vector<int> dist(n + 1, INT_MAX);
dist[1] = 0;
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, 1});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > dist[u]) continue;
for (const auto& edge : adj[u]) {
int v = edge.first;
int w = edge.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
for (int i = 2; i <= n; ++i) {
cout << (dist[i] == INT_MAX ? 1000000000 : dist[i]) << endl;
}
return 0;
}
//AI写的
这里空空如也
有帮助，赞一个