1+ type neighbour struct {
2+ destination int
3+ weight int
4+ }
5+
6+ type heapNode struct {
7+ distance int
8+ nodeIndex int
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 {
51+ return b
52+ }
53+ return a
54+ }
55+
56+ type minHeap []heapNode
57+
58+ func (h minHeap )Len ()int {return len (h ) }
59+ func (h * minHeap )isEmpty ()bool {return len (* h )== 0 }
60+ func (h minHeap )Less (i ,j int )bool {return h [i ].distance < h [j ].distance }
61+ func (h minHeap )Swap (i ,j int ) {h [i ],h [j ]= h [j ],h [i ] }
62+
63+ func (h * minHeap )Push (x interface {}) {
64+ * h = append (* h ,x .(heapNode ))
65+ }
66+
67+ func (h * minHeap )Pop ()interface {} {
68+ l := (* h )[len (* h )- 1 ]
69+ * h = (* h )[:len (* h )- 1 ]
70+ return l
71+ }