I have used Prim’s algorithm , java and am unable to find any test cases that could give me WA here.
public class SpojCStreet {
public static void main(String[] args) {
Scanner sc=null;
int t=0;
sc=new Reader();
t=sc.nextInt();
while(t-->0)
{
graph g=null;
int cost=0;
cost=sc.nextInt();
int n=sc.nextInt();
int m = sc.nextInt();
g = new graph();
for (int i = 0; i < n; i++) {
g.addVertex(new vertex(i + 1));
}
for (int i = 0; i < m; i++) {
vertex src = g.vertexList.get(sc.nextInt() - 1);
vertex dest = g.vertexList.get(sc.nextInt() - 1);
int weight = sc.nextInt();
g.addEdge(src, dest, weight);
}
int h=g.primAlgo()*cost;
System.out.println(h);
}
}
}
class graph
{
public ArrayList<vertex> vertexList;
public int numOfVertices;
public ArrayList<vertex> artPoints;
public ArrayList<LinkedList<edge>> adjList;
public graph() {
vertexList = new ArrayList<>();
adjList = new ArrayList<>();
artPoints=new ArrayList<>();
numOfVertices = 0;
}
public void addVertex(vertex vert) {
vertexList.add(vert);
adjList.add(new LinkedList<>());
numOfVertices++;
}
public void addEdge(vertex source, vertex destination, int weight) {
edge lp = new edge(source, destination,weight);
adjList.get(source.label-1).add(lp);
lp = new edge(destination, source, weight);
adjList.get(destination.label-1).add(lp);
}
public int primAlgo(){
Map<vertex,Boolean> mp=new HashMap<>();
PriorityQueue<vertex> pq=new PriorityQueue<>(new Comparator<vertex>(){
@Override
public int compare(vertex t, vertex t1) {
if(t.value<t1.value)
return -1;
if(t.value==t1.value)
return 0;
else
return 1;
}
});
vertexList.get(0).value=0;
for (int i = 0; i < vertexList.size(); i++) {
pq.add(vertexList.get(i));
}
while(mp.size()!=vertexList.size()){
PriorityQueue<vertex> temp=new PriorityQueue<>(new Comparator<vertex>(){
@Override
public int compare(vertex t, vertex t1) {
if(t.value<t1.value)
return -1;
else if(t.value==t1.value)
return 0;
else
return 1;
}
});
while(!pq.isEmpty())
temp.offer(pq.poll());
while(!temp.isEmpty())
pq.offer(temp.poll());
vertex v=pq.peek();
v.visited=true;
if(mp.containsKey(v))
{
pq.poll();
// System.out.println("popping it");
}
else{
mp.put(v,true);
if(v!=vertexList.get(0))
{
if(v.value==Integer.MAX_VALUE)
v.value=0;
}
LinkedList<edge> lt=adjList.get(v.label-1);
for (edge e: lt) {
if(!e.destination.visited)
{
int min=Math.min(e.destination.value,e.weight);
if(min<e.destination.value)
{
e.destination.value=min;
// pq.add(e.destination);
}
}
}
}
}
int sum=0;
for (int i = 0; i < vertexList.size(); i++) {
sum+=vertexList.get(i).value;
}
return sum;
}
}
class vertex {
public int label;
public int value;
public boolean visited;
public vertex(int label) {
this.label = label;
this.value=Integer.MAX_VALUE;
this.visited=false;
}
}
class edge {
vertex source, destination;
int weight;
public edge(vertex source, vertex destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
/*
1
1
6
9
1 2 5
1 3 10
1 6 15
2 4 2
2 5 7
4 5 3
5 6 1
1 4 16
3 6 10
1
1
6 10
1 2 5
2 6 10
2 3 3
3 5 6
4 5
1
2 5 6
1 5 7
1 4 5
3 6 12
5 6 3
*/