Commit542c2c8

authored

Merge pull requestneetcode-gh#1937 from kkr2/feat/1584-min-cost-to-connect.go

Create 1584-min-cost-to-connect.go

2 parentsc78ef30 +5a6b0a7 commit542c2c8Copy full SHA for 542c2c8

File tree

+64

-0

lines changed

+64

-0

lines changed

Lines changed: 64 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,64 @@`
	`1`	`+funcminCostConnectPoints(points [][]int)int {`
	`2`	`+`
	`3`	`+n:=len(points)`
	`4`	`+adj:=make([][][]int,n)`
	`5`	`+fori:=0;i<n;i++ {`
	`6`	`+x1,y1:=points[i][0],points[i][1]`
	`7`	`+forj:=i+1;j<n;j++ {`
	`8`	`+x2,y2:=points[j][0],points[j][1]`
	`9`	`+dist:=abs(x1-x2)+abs(y1-y2)`
	`10`	`+adj[i]=append(adj[i], []int{dist,j})`
	`11`	`+adj[j]=append(adj[j], []int{dist,i})`
	`12`	`+}`
	`13`	`+}`
	`14`	`+// prims`
	`15`	`+res:=0`
	`16`	`+visited:=make(map[int]bool)`
	`17`	`+`
	`18`	`+h:=&IntHeap{[2]int{0,0}}`
	`19`	`+`
	`20`	`+forlen(visited)<n {`
	`21`	`+pntObj:=heap.Pop(h).([2]int)`
	`22`	`+cost,pnt:=pntObj[0],pntObj[1]`
	`23`	`+`
	`24`	`+ifvisited[pnt] {`
	`25`	`+continue`
	`26`	`+}`
	`27`	`+res+=cost`
	`28`	`+visited[pnt]=true`
	`29`	`+`
	`30`	`+for_,neighbour:=rangeadj[pnt] {`
	`31`	`+nCost,nPoint:=neighbour[0],neighbour[1]`
	`32`	`+`
	`33`	`+if!visited[nPoint] {`
	`34`	`+heap.Push(h, [2]int{nCost,nPoint})`
	`35`	`+}`
	`36`	`+}`
	`37`	`+}`
	`38`	`+returnres`
	`39`	`+}`
	`40`	`+`
	`41`	`+funcabs(nint)int {`
	`42`	`+ifn>0 {`
	`43`	`+returnn`
	`44`	`+}`
	`45`	`+return-n`
	`46`	`+}`
	`47`	`+`
	`48`	`+typeIntHeap [][2]int`
	`49`	`+`
	`50`	`+func (hIntHeap)Len()int {returnlen(h) }`
	`51`	`+func (hIntHeap)Less(i,jint)bool {returnh[i][0]<h[j][0] }`
	`52`	`+func (hIntHeap)Swap(i,jint) {h[i],h[j]=h[j],h[i] }`
	`53`	`+`
	`54`	`+func (h*IntHeap)Push(xinterface{}) {`
	`55`	`+h=append(h,x.([2]int))`
	`56`	`+}`
	`57`	`+`
	`58`	`+func (h*IntHeap)Pop()interface{} {`
	`59`	`+old:=*h`
	`60`	`+n:=len(old)`
	`61`	`+x:=old[n-1]`
	`62`	`+*h=old[:n-1]`
	`63`	`+returnx`
	`64`	`+}`

Comments

(0)