743 网络延迟时间

题目链接

743. 网络延迟时间

分析

单源最短路问题，建图后计算出所有节点最短路径，节点最短路径的最大值即为答案

使用链式前向星存图，用 Dijkstra 算法计算每个节点的最短路长度

最后，取最大值即可（如最大值是 $\infty$ 代表有节点无法到达，返回 $-1$ 即可

代码实现

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        const int MAXN = 6010;
        int head[105], nxt[MAXN], weight[MAXN], to[MAXN], idx = 0;
        memset(head, -1, sizeof(head));
        for(auto &v : times)
        {
            nxt[idx] = head[v[0]];
            to[idx] = v[1];
            weight[idx] = v[2];
            head[v[0]] = idx++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        vector<bool> isVis(n + 1, false);
        vector<int> dis(n + 1, INT_MAX);
        pq.emplace(0, k);
        dis[k] = 0, dis[0] = 0; // 将未使用的位设为 0，防止计算最大值出错 
        while(!pq.empty())
        {
            auto [d, u] = pq.top();
            pq.pop();
            if(isVis[u])
                continue;
            isVis[u] = true;
            for(int i = head[u]; ~i; i = nxt[i])
            {
                int t = d + weight[i];
                if(t < dis[to[i]])
                {
                    dis[to[i]] = t;
                    pq.emplace(t, to[i]);
                }
            }
  
        }
        int ans = ranges::max(dis);
        return ans < INT_MAX ? ans : -1;
        return 0;
    }
};

复杂度分析

• 时间复杂度：$O(m \log m)$，$m$ 为 $times$ 的长度，由于堆中可能有相同节点，最坏情况即 $times$ 中路径均进入堆中
• 空间复杂度：$O(m)$