leetcode 743 | 网络延迟时间（图入门）

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>

#define INT_MAX 2147483647
#define min(a, b) (a < b ? a : b)
#define max(a, b) (a > b ? a : b)

/*
N是网络节点数（1-N）
K是起始节点
返回值：
返回从K到所有节点的最短时间
*/
int networkDelayTime(int **times, int timesRowSize, int timesColSize, int N, int K)
{
    int dist[N + 1];

    for (int i = 0; i < N + 1; ++i)
    {
        //初始化K到每个节点的距离为最大值
        dist[i] = INT_MAX;
    }

    //到自己的距离为0
    dist[K] = 0;

    int loop = 1;

    while (loop--)
    {
        //遍历所有边
        for (int i = 0; i < timesRowSize; i++)
        {
            //寻找变化的节点
            if (dist[times[i][0]] != INT_MAX)
            {
                int u = dist[times[i][0]];
                int v = dist[times[i][1]];
                int w = times[i][2];
                //更新较小路径
                dist[times[i][1]] = min(u + w, v);
                //存在更新
                if (v != dist[times[i][1]])
                    loop = 1;
            }
        }
    }

    int max_num = 0;

    //取得距离K节点最远的值
    for (int i = 1; i <= N; i++)
    {
        if (dist[i] == INT_MAX)
            return -1;

        max_num = max(max_num, dist[i]);
    }

    return max_num;
}