743. Network Delay Time (swift, python)

743. Network Delay Time (swift, python)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

typealias nodeTuple = ( Int , Int ) class Solution { func networkDelayTime(_ times: [[ Int ]], _ n: Int , _ k: Int ) - > Int { var graph = Array(repeating: [nodeTuple](), count: n + 1 ) var distance: [ Int ] = Array(repeating: Int ( 1e9 ), count: n + 1 ) for time in times { graph[time[ 0 ]].append((time[ 1 ], time[ 2 ])) } var queue: [nodeTuple] = [] queue.append(( 0 , k)) distance[k] = 0 while ! queue.isEmpty { queue.sort(by: { $0. 0 > $1. 0 }) let tuple: nodeTuple = queue.removeFirst() let dist: Int = tuple. 0 let now: Int = tuple. 1 if distance[now] < dist { continue } for g in graph[now] { let cost: Int = dist + g. 1 if cost < distance[g. 0 ] { distance[g. 0 ] = cost queue.append((cost, g. 0 )) } } } var answer: Int = 0 for i in 1. ..n { answer = max(answer, distance[i]) } // 최단거리를 담는 배열에 INF와 같은 값이 있다면 k에서 모든 노드를 방문할 수 없다는 뜻이므로 // -1을 리턴 if answer = = Int ( 1e9 ) { return - 1 } return answer } } let sol = Solution() print (sol.networkDelayTime([[ 2 , 1 , 1 ],[ 2 , 3 , 1 ],[ 3 , 4 , 1 ]], 4 , 2 )) Colored by Color Scripter

from http://one10004.tistory.com/81 by ccl(A) rewrite - 2021-11-03 12:27:04