leetcode 743. Network Delay Time 图最短路径 + Bellman Ford 算法

﹏ヽ暗。殇╰゛Y 2022-06-03 09:56 91阅读 0赞

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times\[i\] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Note:  
N will be in the range \[1, 100\].  
K will be in the range \[1, N\].  
The length of times will be in the range \[1, 6000\].  
All edges times\[i\] = (u, v, w) will have 1 <= u, v <= N and 1 <= w <= 100.

本题题意很简单，起初我还愣了一下，看到网上的一个做法才明白这是一个基本的权重图最短路径的计算问题，看来还有很多东西待复习啊，真心差得很多，加油吧！

注意第一个循环其实可以做n-1次，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        int networkDelayTime(vector<vector<int>>& times, int n, int k)
        {
            vector<int> dist(n + 1, INT_MAX);
            dist[k] = 0;
            for (int i = 0; i < n; i++)
            {
                for (auto a : times)
                {
                    int from = a[0], to = a[1], value = a[2];
                    if (dist[from] != INT_MAX && dist[to] > dist[from] + value)
                        dist[to] = dist[from] + value;
                }
            }
    
            int maxTime = 0;
            for(int i=1;i<=n;i++)
                maxTime = max(maxTime, dist[i]);
            return maxTime == INT_MAX ? -1 : maxTime;
        }
    };