743. 网络延迟时间 有 n 个网络节点,标记为 1 到 n。 给你一个列表 times,表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi),其中 ui 是源节点,

  1. 网络延迟时间
    有 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;
    }
};

上一篇:2021-03-07 C++常用回调函数less和greater——在sort和priority的应用


下一篇:linux线程