We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
packagemainimport("bufio""fmt""io""os""strconv""strings")const(VISITEDint32=1UNVISITEDint32=-1)/* * Complete the 'roadsAndLibraries' function below. * * The function is expected to return a LONG_INTEGER. * The function accepts following parameters: * 1. INTEGER n * 2. INTEGER c_lib * 3. INTEGER c_road * 4. 2D_INTEGER_ARRAY cities */funcroadsAndLibraries(nint32,c_libint32,c_roadint32,cities[][]int32)int64{dfsNum:=initDfsNum(n)adjList:=edgeListToAdjList(n,cities)citiesWithoutLibrary:=int64(0)roadsNeeded:=int64(0)librariesNeeded:=int64(0)fori:=int32(1);i<=n;i++{ifdfsNum[i]==UNVISITED{librariesNeeded++citiesWithoutLibrary+=(dfs(i,adjList,dfsNum)-1)}}ifc_lib<c_road{librariesNeeded+=citiesWithoutLibrary}else{roadsNeeded+=citiesWithoutLibrary}return(roadsNeeded*int64(c_road))+(librariesNeeded*int64(c_lib))}funcdfs(uint32,adjList[][]int32,dfsNum[]int32)int64{dfsNum[u]=VISITEDsizeOfComponent:=int64(1)fori:=0;i<len(adjList[u]);i++{v:=adjList[u][i]ifdfsNum[v]==UNVISITED{sizeOfComponent+=dfs(v,adjList,dfsNum)}}returnsizeOfComponent}funcinitDfsNum(vint32)[]int32{dfsNum:=make([]int32,v+1)fori:=1;i<=int(v);i++{dfsNum[i]=UNVISITED}returndfsNum}funcedgeListToAdjList(vint32,edgeList[][]int32)[][]int32{adjList:=make([][]int32,v+1)for_,edge:=rangeedgeList{u:=edge[0]v:=edge[1]adjList[u]=append(adjList[u],v)adjList[v]=append(adjList[v],u)}returnadjList}funcmain(){reader:=bufio.NewReaderSize(os.Stdin,16*1024*1024)stdout,err:=os.Create(os.Getenv("OUTPUT_PATH"))checkError(err)deferstdout.Close()writer:=bufio.NewWriterSize(stdout,16*1024*1024)qTemp,err:=strconv.ParseInt(strings.TrimSpace(readLine(reader)),10,64)checkError(err)q:=int32(qTemp)forqItr:=0;qItr<int(q);qItr++{firstMultipleInput:=strings.Split(strings.TrimSpace(readLine(reader))," ")nTemp,err:=strconv.ParseInt(firstMultipleInput[0],10,64)checkError(err)n:=int32(nTemp)mTemp,err:=strconv.ParseInt(firstMultipleInput[1],10,64)checkError(err)m:=int32(mTemp)c_libTemp,err:=strconv.ParseInt(firstMultipleInput[2],10,64)checkError(err)c_lib:=int32(c_libTemp)c_roadTemp,err:=strconv.ParseInt(firstMultipleInput[3],10,64)checkError(err)c_road:=int32(c_roadTemp)varcities[][]int32fori:=0;i<int(m);i++{citiesRowTemp:=strings.Split(strings.TrimRight(readLine(reader)," \t\r\n")," ")varcitiesRow[]int32for_,citiesRowItem:=rangecitiesRowTemp{citiesItemTemp,err:=strconv.ParseInt(citiesRowItem,10,64)checkError(err)citiesItem:=int32(citiesItemTemp)citiesRow=append(citiesRow,citiesItem)}iflen(citiesRow)!=2{panic("Bad input")}cities=append(cities,citiesRow)}result:=roadsAndLibraries(n,c_lib,c_road,cities)fmt.Fprintf(writer,"%d\n",result)}writer.Flush()}funcreadLine(reader*bufio.Reader)string{str,_,err:=reader.ReadLine()iferr==io.EOF{return""}returnstrings.TrimRight(string(str),"\r\n")}funccheckError(errerror){iferr!=nil{panic(err)}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
My Golang solution: