743. Network Delay Time

class Solution {public: ???int networkDelayTime(vector<vector<int>>& times, int N, int K) { ???????const int MAX_TIME = 101 * 100; ???????vector<int> dist(N, MAX_TIME); ???????dist[K-1] = 0; ???????for (int i = 0; i < N; ++i) { ???????????for (auto time : times) { ???????????????int u = time[0]-1, v = time[1] - 1, w = time[2]; ???????????????dist[v] = min(dist[v], dist[u] + w); ???????????} ???????} ???????int temp = *max_element(dist.begin(), dist.end()); ???????return temp == MAX_TIME ? -1 : temp; ???}};

// Author: Huahua// Runtime: 89 msclass Solution {public: ???int networkDelayTime(vector<vector<int>>& times, int N, int K) { ???????constexpr int MAX_TIME = 101 * 100; ???????vector<vector<int>> d(N, vector<int>(N, MAX_TIME)); ???????????????for (auto time : times) ??????????????d[time[0] - 1][time[1] - 1] = time[2]; ???????????????for (int i = 0; i < N; ++i) ???????????d[i][i] = 0; ???????????????for (int k = 0; k < N; ++k) ???????????for (int i = 0; i < N; ++i) ???????????????for (int j = 0; j < N; ++j) ???????????????????????????????????????d[i][j] = min(d[i][j], d[i][k] + d[k][j]); ???????????????int max_time = *max_element(d[K - 1].begin(), d[K - 1].end()); ???????????????return max_time >= MAX_TIME ? - 1 : max_time; ???}};

class Solution { ???Map<Integer, Integer> dist; ???public int networkDelayTime(int[][] times, int N, int K) { ???????Map<Integer, List<int[]>> graph = new HashMap(); ???????for (int[] edge : times) { ???????????if (!graph.containsKey(edge[0])) { ???????????????graph.put(edge[0], new ArrayList<int[]>()); ???????????} ???????????graph.get(edge[0]).add(new int[]{edge[1], edge[2]}); ???????} ???????dist = new HashMap(); ???????for (int node = 1; node <= N; ++node) { ???????????dist.put(node, Integer.MAX_VALUE); ???????} ???????dist.put(K, 0); ???????boolean[] seen = new boolean[N+1]; ???????while (true) { ???????????int candNode = -1; ???????????int candDist = Integer.MAX_VALUE; ???????????for (int i = 1; i <= N; ++i) { ???????????????if (!seen[i] && dist.get(i) < candDist) { ???????????????????candDist = dist.get(i); ???????????????????candNode = i; ???????????????} ???????????} ???????????if (candNode < 0) break; ???????????seen[candNode] = true; ???????????if (graph.containsKey(candNode)) { ???????????????for (int[] info : graph.get(candNode)) ???????????????????dist.put(info[0], Math.min(dist.get(info[0]), dist.get(candNode) + info[1])); ???????????} ???????} ???????int ans = 0; ???????for (int cand : dist.values()) { ???????????if (cand == Integer.MAX_VALUE) return -1; ???????????ans = Math.max(ans, cand); ???????} ???????return ans; ???}}

class Solution(object): ???def networkDelayTime(self, times, N, K): ???????""" ???????:type times: List[List[int]] ???????:type N: int ???????:type K: int ???????:rtype: int ???????""" ???????graph = collections.defaultdict(list) ???????????????for u, v, w in times: ???????????graph[u].append((w, v)) ???????????????????dist = {node: float(‘inf‘) for node in xrange(1, N+1)} ???????????????def dfs(node, elapsed): ???????????if elapsed >= dist[node]: return ???????????dist[node] = elapsed ???????????for time, nei in sorted(graph[node]): ???????????????dfs(nei, elapsed + time) ???????????????????dfs(K, 0) ???????????????ans = max(dist.values()) ???????return ans if ans < float(‘inf‘) else -1 ???