Q26 Network Delay Time - LeetCode 743
Fri Apr 28 2023 06:41:29 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
/*Q26 graph playlist ,bellman ford
we are not using any temp array here as we dont need result of every iteration
we just need minimum path from source to every dest and
we will return max of all min-paths as our answer
*/
int path[] = new int[n];
Arrays.fill(path , Integer.MAX_VALUE);
path[k-1] = 0;
int ans = -1;
for(int i = 0 ;i < n-1 ; i++){
for(int time[] : times){
int u = time[0] , v = time[1] , wt = time[2];
if(path[u-1] == Integer.MAX_VALUE)
continue;
//turned into 0 based indexing
path[v-1] = Math.min(path[v-1] ,path[u-1] + wt );
}
}
//finding maximum of all min paths
for(int i = 0 ;i < n ; i++)
ans = Math.max(ans , path[i]);
//if any min path is still max_Value we return -1
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}
content_copyCOPY
https://leetcode.com/problems/network-delay-time/
Comments