Commit959193e

authored

Merge pull requestneetcode-gh#1938 from kkr2/feat/0743-network-delay-time.go

Create 0743-network-delay-time.go

2 parents9846b55 +2820036 commit959193eCopy full SHA for 959193e

File tree

1 file changed

+71

-0

lines changed

go
- 0743-network-delay-time.go

1 file changed

+71

-0

lines changed

`‎go/0743-network-delay-time.go‎`

Lines changed: 71 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,71 @@`
	`1`	`+typeneighbourstruct {`
	`2`	`+destinationint`
	`3`	`+weightint`
	`4`	`+}`
	`5`	`+`
	`6`	`+typeheapNodestruct {`
	`7`	`+distanceint`
	`8`	`+nodeIndexint`
	`9`	`+}`
	`10`	`+`
	`11`	`+funcnetworkDelayTime(times [][]int,nint,kint)int {`
	`12`	`+edgeMap:=make(map[int][]neighbour)`
	`13`	`+for_,log:=rangetimes {`
	`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`	`+ifvis:=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:=rangeneighbours {`
	`35`	`+ifvis:=visited[neigh.destination];!vis {`
	`36`	`+heap.Push(h,heapNode{`
	`37`	`+distance:neigh.weight+hNode.distance,`
	`38`	`+nodeIndex:neigh.destination})`
	`39`	`+}`
	`40`	`+}`
	`41`	`+}`
	`42`	`+`
	`43`	`+ifn==len(visited) {`
	`44`	`+returnt`
	`45`	`+}`
	`46`	`+return-1`
	`47`	`+}`
	`48`	`+`
	`49`	`+funcmax(a,bint)int {`
	`50`	`+ifa<b {`
	`51`	`+returnb`
	`52`	`+}`
	`53`	`+returna`
	`54`	`+}`
	`55`	`+`
	`56`	`+typeminHeap []heapNode`
	`57`	`+`
	`58`	`+func (hminHeap)Len()int {returnlen(h) }`
	`59`	`+func (hminHeap)isEmpty()bool {returnlen(h)==0 }`
	`60`	`+func (hminHeap)Less(i,jint)bool {returnh[i].distance<h[j].distance }`
	`61`	`+func (hminHeap)Swap(i,jint) {h[i],h[j]=h[j],h[i] }`
	`62`	`+`
	`63`	`+func (h*minHeap)Push(xinterface{}) {`
	`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`	`+returnl`
	`71`	`+}`

0 commit comments

Comments

(0)

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Commit959193e

File tree

1 file changed

1 file changed

`‎go/0743-network-delay-time.go‎`

0 commit comments