LeetCode 743. 网络延迟时间（最短路径）

示例：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
输出：2
 
注意:
N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。

class Solution {	//C++
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
    	vector<vector<int>> cost(N+1,vector<int>(N+1,INT_MAX));
    	for(auto& t : times)
    		cost[t[0]][t[1]] = t[2];
    	int i,j,k;
        for(k = 1; k <= N; ++k)
            for(i = 1; i <= N; ++i)
            {
                for(j = 1; j <= N; ++j)
                {
                    if(cost[i][k] != INT_MAX && cost[k][j] != INT_MAX
                        && cost[i][j] > cost[i][k]+cost[k][j])
                    {
                        cost[i][j] = cost[i][k]+cost[k][j];
                    }
                }
            }
    	int maxt = 0;
    	for(i = 1; i <= N; ++i)
    	{
            if(i == K)
                continue;
    		if(cost[K][i] == INT_MAX)
    			return -1;
    		maxt = max(maxt, cost[K][i]);
    	}
    	return maxt;
    }
};