力扣743题 网络延迟时间
有 n 个网络节点，标记为 1 到 n。 给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (u(i), v(i), w(i))，其中 u(i) 是源节点，v(i) 是目标节点， w(i) 是一个信号从源节点传递到目标节点的时间。 现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int networkDelayTime(vector<vector<int>>& times, int n, int k, vector<int>& parent) {
vector<vector<pair<int, int>>> g(n);
for (auto& e : times) {
int x = e[0] - 1, y = e[1] - 1, wt = e[2];
g[x].emplace_back(y, wt);
}
vector<int> dis(n, INT_MAX);
dis[k - 1] = 0;
parent.assign(n, -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.emplace(0, k - 1);
while (!pq.empty()) {
auto [dx, u] = pq.top();
pq.pop();
if (dx > dis[u]) continue;
for (auto& [v, w] : g[u]) {
int new_dis = dx + w;
if (new_dis < dis[v]) {
dis[v] = new_dis;
parent[v] = u;
pq.emplace(new_dis, v);
}
}
}
int max_dis = INT_MIN;
for (int d : dis) {
if (d == INT_MAX) return -1;
max_dis = max(max_dis, d);
}
return max_dis;
}
};
vector<int> reconstructPath(int target, const vector<int>& parent) {
vector<int> path;
for (int cur = target; cur != -1; cur = parent[cur]) {
path.push_back(cur + 1);
}
reverse(path.begin(), path.end());
return path;
}
int main() {
int n = 4, k = 2;
vector<vector<int>> times = { {2, 1, 1}, {2, 3, 1}, {3, 4, 1} };
vector<int> parent;
Solution s;
int max_time = s.networkDelayTime(times, n, k, parent);
cout << "min_time: " << max_time << endl << endl;
cout << "start node: " << k << endl << endl;
if (max_time == -1) {
cout << "Warning: Some nodes are unreachable!" << endl << endl;
}
cout << "Shortest paths:" << endl;
for (int i = 0; i < n; ++i) {
vector<int> path = reconstructPath(i, parent);
cout << "To node " << (i + 1) << ": ";
// 正确判断可达性：路径第一个节点应为起点k
if (path.empty() || path[0] != k) {
cout << "unreachable";
} else {
for (int node : path) {
cout << node;
if (node != path.back()) cout << " to ";
}
}
cout << endl;
}
}
min_time: 2
start node: 2
Shortest paths:
To node 1: 2 to 1
To node 2: 2
To node 3: 2 to 3
To node 4: 2 to 3 to 4
