| 9 | } |
| 10 | |
| 11 | func networkDelayTime(times [][]int, n int, k int) int { |
| 12 | edgeMap := make(map[int][]neighbour) |
| 13 | for _, log := range times { |
| 14 | edgeMap[log[0]] = append(edgeMap[log[0]], neighbour{destination: log[1], weight: log[2]}) |
| 15 | } |
| 16 | |
| 17 | h := &minHeap{heapNode{distance: 0, nodeIndex: k}} |
| 18 | heap.Init(h) |
| 19 | visited := make(map[int]bool) |
| 20 | t := 0 |
| 21 | |
| 22 | for !h.isEmpty() { |
| 23 | hNode := heap.Pop(h).(heapNode) |
| 24 | |
| 25 | if vis := visited[hNode.nodeIndex]; vis { |
| 26 | continue |
| 27 | } |
| 28 | |
| 29 | t = max(t, hNode.distance) |
| 30 | |
| 31 | visited[hNode.nodeIndex] = true |
| 32 | |
| 33 | neighbours := edgeMap[hNode.nodeIndex] |
| 34 | for _, neigh := range neighbours { |
| 35 | if vis := visited[neigh.destination]; !vis { |
| 36 | heap.Push(h, heapNode{ |
| 37 | distance: neigh.weight + hNode.distance, |
| 38 | nodeIndex: neigh.destination}) |
| 39 | } |
| 40 | } |
| 41 | } |
| 42 | |
| 43 | if n == len(visited) { |
| 44 | return t |
| 45 | } |
| 46 | return -1 |
| 47 | } |
| 48 | |
| 49 | func max(a, b int) int { |
| 50 | if a < b { |