泉州市知名网站建设公司,黑龙江省营商环境建设监督局网站,做做网站已更新,网页设计师培训水公司文章目录1. 题目2. 解题2.1 弗洛伊德1. 题目
有 N 个网络节点#xff0c;标记为 1 到 N。
给定一个列表 times#xff0c;表示信号经过有向边的传递时间。 times[i] (u, v, w)#xff0c;其中 u 是源节点#xff0c;v 是目标节点#xff0c; w 是一个信号从源节点传递到…
文章目录1. 题目2. 解题2.1 弗洛伊德1. 题目
有 N 个网络节点标记为 1 到 N。
给定一个列表 times表示信号经过有向边的传递时间。 times[i] (u, v, w)其中 u 是源节点v 是目标节点 w 是一个信号从源节点传递到目标节点的时间。
现在我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号 如果不能使所有节点收到信号返回 -1。 示例
输入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。来源力扣LeetCode 链接https://leetcode-cn.com/problems/network-delay-time 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 弗洛伊德
class Solution { //C
public:int networkDelayTime(vectorvectorint times, int N, int K) {vectorvectorint cost(N1,vectorint(N1,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;}
};308 ms 26.4 MB
