Q21 Water Supply In A Village - Coding Ninjas
Thu Apr 27 2023 10:21:17 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.ArrayList;
import java.util.PriorityQueue;
public class Solution {
public static int supplyWater(int n, int k, int[] wells, int[][] pipes) {
/* Q21 graph playlist , we add Node 0 , as dummy node which
acts as our wells edge for each wedge and then we find
MST for the whole graph
*/
//making graph of pipes
ArrayList<ArrayList<pair>> graph = new ArrayList<>();
//initializing AL
for(int i = 0 ;i <= n ; i++)
graph.add(new ArrayList<>());
for(int pipe[] : pipes){
graph.get(pipe[0]).add(new pair(pipe[1],pipe[2]));
graph.get(pipe[1]).add(new pair(pipe[0],pipe[2]));
}
//now adding Wells edge in graph for each vertex
for(int i = 0 ;i < n ; i++){
graph.get(i+1).add(new pair(0 , wells[i]));
graph.get(0).add(new pair(i+1 , wells[i]));
}
//now running prims algo for MST
PriorityQueue<pair> pq = new PriorityQueue<>();
pq.add(new pair(0,0));
boolean visited[] = new boolean[n + 1];
int ans = 0;
while(pq.size() > 0){
pair rem = pq.remove();
int vtx = rem.vtx , wt = rem.wt;
if(visited[vtx] == true){
continue;
}
ans += wt;
visited[vtx] = true;
//adding neighours
for(pair nbrs : graph.get(vtx)){
if(visited[nbrs.vtx] == false)
pq.add(nbrs);
}
}
return ans;
}
public static class pair implements Comparable<pair>{
int vtx , wt;
pair(){
}
pair(int vtx , int wt){
this.vtx = vtx;
this.wt = wt;
}
public int compareTo(pair o){
return this.wt - o.wt;
}
}
}
content_copyCOPY
https://www.codingninjas.com/codestudio/problems/water-supply-in-a-village_1380956
Comments