第16题：网络延迟时间

本文主要是介绍第16题：网络延迟时间，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

解题思路：先写一个比较函数，用于得到最小值，用Dijkstra算法算出源点到所有点的最短路径，再取最长的那个返回即可

源代码：

struct MyStruct {

    int pos;

    int time;

    //  比较函数, 在优先队列里, 将较小的排在尾部, top()得到的就是队列里面最小值

    bool operator<(const MyStruct &a) const

    {

        return time > a.time;

    }

};

class Solution {

public:

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {

 unordered_map<int, vector<pair<int, int>>> myMap;

        for (const auto &element : times) {

            myMap[element[0]].push_back({element[1], element[2]});

        }

        // 存储最后的结果

        vector<int> pos(n + 1, INT_MAX);

        // 位置0是特殊处理, k点time初始化为0

        pos[0] = 0;

        pos[k] = 0;

        priority_queue<MyStruct> myQueue;

        // 将起点能一步到达的位置存入优先队列

        for (auto i = 0; i < myMap[k].size(); ++i) {

            myQueue.push({myMap[k][i].first, myMap[k][i].second});

            pos[myMap[k][i].first] = myMap[k][i].second;

        }

        vector<int> visited(n + 1, 0); // 标记已经处理的点

        visited[0] = 1;

        visited[k] = 1;

        while (myQueue.empty() == false) {

            auto [first, second] = myQueue.top(); // 得到当前能到达的最近距离的点 first是此点 second是k点到此点的最短距离

            myQueue.pop();

            visited[first] = 1; // 标记已经处理此点

            for (auto i = 0; i < myMap[first].size(); ++i) {

                if (visited[myMap[first][i].first] == 1) {

                    continue; // 已经处理的点不再访问

                }

                // 将此点能到达的下一个节点存入优先队列

                myQueue.push({myMap[first][i].first, second + myMap[first][i].second});

                pos[myMap[first][i].first] = min(second + myMap[first][i].second, pos[myMap[first][i].first]); // 更新最短距离

            }

        }

        auto maxElement = *max_element(pos.begin(), pos.end());

        if (maxElement == INT_MAX) {

            return -1;

        }

        return maxElement;

    }

};

运行结果：

这篇关于第16题：网络延迟时间的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！