743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

提示：

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= ui, vi <= n
• ui != vi
• 0 <= wi <= 100
• 所有 (ui, vi) 对都 互不相同（即，不含重复边）

 

 

int networkDelayTime(vector<vector<int>>& times, int n, int k)
{
    vector< vector<int>>Vec(n+1,vector<int>(n+1, INT32_MAX/2));
    vector<int>vec(n + 1, INT32_MAX/2);
    vector<int>visited(n + 1, false);
    
    for (int i = 0; i < times.size(); i++)
    {
        int m = times[i][0];
        int n= times[i][1];
        int k = times[i][2];
        Vec[m][n] = k;
    }
    vec[k] = 0;

//找最小值
    for (int i = 1; i < n+1; i++)
    {
        int m = 1;
        int tmp = INT32_MAX / 2;
        for (int j = 1; j < n + 1; j++)
        {
            if (true == visited[j])
            {
                continue;
            }
            if ( tmp > vec[j]) 
            {
                m = j;
                tmp = vec[j];
            }

        }

//确定节点，不用再次访问
        visited[m] = true; 

//找最小值到其他节点距离
        for (int j = 0; j < n + 1; j++)
        {
            vec[j] = vec[j]>vec[m] + Vec[m][j] ? vec[m] + Vec[m][j] : vec[j];
        }
    }

//找最大时间的

    int count = 0;
    int ret = INT32_MIN;
    for (int i = 1; i < vec.size(); i++)
    {
        if (vec[i] == INT32_MAX/2)
        {
            continue;
        }
        count++;
        if (vec[i] > ret)
        {
            ret = vec[i];
        }
    }
    if (count == n)
    {
        return ret;
    }
    else
    {
        return -1;
    }

}