- 网络延迟时间
有 n 个网络节点,标记为 1 到 n。
给你一个列表 times,表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi),其中 ui 是源节点,vi 是目标节点, wi 是一个信号从源节点传递到目标节点的时间。
现在,从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号?如果不能使所有节点收到信号,返回 -1 。
class Solution {
public:
vector<vector<pair<int, int>>> nei;
vector<bool> status;
vector<int> priority;
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
nei.resize(n);
status.resize(n, false);
priority.resize(n, __INT_MAX__);
for (auto t : times) {
nei[t[0]-1].push_back(make_pair(t[1]-1, t[2]));
}
k--;
priority[k] = 0;
status[k] = true;
while (true) {
for (auto v : nei[k]) {
if (!status[v.first] && priority[v.first] > priority[k] + v.second) {
priority[v.first] = priority[k] + v.second;
}
}
for (int shortest = __INT_MAX__, j = 0; j < n; j++) {
if (!status[j] && shortest > priority[j]) {
shortest = priority[j];
k = j;
}
}
if (status[k]) {
break;
}
status[k] = true;
}
for (auto s : status) {
if (!s) {
return -1;
}
}
int res = priority[0];
for (auto p : priority) {
res = max(res, p);
}
return res;
}
};