LeetCode 743 Network Delay Time

    
        标签：
        
            图算法
        
            LeetCode
        
    发布于：2022-02-09 22:57:21
    编辑于：2022-02-09 23:52:07
    浏览量：786

概述

https://leetcode.com/problems/network-delay-time/

Dijkstra 最短路径算法

属实离谱，写错两次。时间复杂度 O(n^2)。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>> graph(n + 1, vector<int>(n + 1, INT_MAX));
        for (auto time : times) {
            graph[time[0]][time[1]] = time[2];
        }
        vector<int> d(n + 1, INT_MAX);
        vector<int> fixed(n + 1, false);
        d[k] = 0;
        
        while (true) {
            fixed[k] = true;
            int minIdx = -1;
            int minVal = INT_MAX;
            for (int i = 1; i <= n; i ++) {
                if (!fixed[i]) {
                    if (graph[k][i] != INT_MAX) {  // 第二次写错：当时该条件与上面那个写一起了
                        d[i] = min(d[i], d[k] + graph[k][i]);
                    }
                    if (d[i] < minVal) {
                        minVal = d[i];  // 第一次写错：忘记更新 minVal 了
                        minIdx = i;
                    }
                }
            }
            if (minIdx == -1) break;
            k = minIdx;
        }
        int maxCost = 0;
        for (int i = 1; i <= n; i ++) {
            if (d[i] == INT_MAX) return -1;
            maxCost = max(maxCost, d[i]);
        }
        return maxCost;
    }
};

Links: leetcode-743-network-delay-time