why it give wrong answer?? how to debig it??
import java.util.*;
class HeapGeneric< T extends Comparable> {
ArrayList data=new ArrayList<>();
HashMap<T,Integer> map=new HashMap<>();
public void add(T item)
{
data.add(item);
map.put(item,this.data.size()-1);
upheapify(this.data.size()-1);
}
public void updatepriority(T item)
{
int index=map.get(item);
upheapify(index);
}
public T remove()
{
swap(0,this.data.size()-1);
T rv=this.data.remove(this.data.size()-1);
downheapify(0);
map.remove(rv);
return rv;
}
private void downheapify(int pi)
{
int lc=2*pi+1;
int rc=2*pi+2;
int mini=pi;
if(lc < this.data.size() && isLarger(data.get(lc),data.get(mini)) >0)
mini=pi;
if(rc <data.size() && isLarger(data.get(rc),data.get(mini)) >0)
mini=pi;
if(mini!=pi)
{
swap(mini,pi);
downheapify(mini);
}
}
private void upheapify(int c)
{
int pi=(c-1)/2;
if(isLarger(data.get(c),data.get(pi)) > 0)
{
swap(pi,c);
upheapify(pi);
}
}
private void swap(int i,int j)
{
T ith=data.get(i);
T jth=data.get(j);
data.set(i,jth);
data.set(j,ith);
map.put(ith,j);
map.put(jth,i);
}
public int isLarger(T t,T o)
{
return t.compareTo(o);
}
public boolean isEmpty()
{
return this.data.size()==0;
}
}
class DijkstraPair implements Comparable< DijkstraPair> {
int vname;
String psf;
int cost;
public int compareTo(DijkstraPair o)
{
return o.cost-this.cost;
}
}
public class Graph {
private int size=0;
private int sizeE=0;
private class Vertex{
HashMap<Integer,Integer> nbrs=new HashMap<>();
}
HashMap<Integer,Vertex> vtces;
public Graph(){
vtces=new HashMap<>();
}
public void addVertex(int vname)
{ size++;
Vertex vt=new Vertex();
vtces.put(vname,vt);
}
public void addEdge(int a,int b,int cost)
{ sizeE++;
if(!vtces.containsKey(a))
this.addVertex(a);
Vertex v1=vtces.get(a);
v1.nbrs.put(b,cost);
if(!vtces.containsKey(b))
this.addVertex(b);
Vertex v2=vtces.get(b);
v2.nbrs.put(a,cost);
}
public HashMap<Integer,Integer> dijkstra(int src){
HashMap<Integer,Integer> ans=new HashMap<>();
HashMap<Integer,DijkstraPair> map=new HashMap<>();
HeapGeneric<DijkstraPair> heap=new HeapGeneric<>();
for(int key: vtces.keySet())
{
DijkstraPair np=new DijkstraPair();
np.vname=key;
np.cost=Integer.MAX_VALUE;
np.psf="";
if(key==src)
{
np.cost=0;
np.psf=np.psf+key;
}
heap.add(np);
map.put(key,np);
}
while(!heap.isEmpty())
{
DijkstraPair rp=heap.remove();
map.remove(rp.vname);
if(rp.psf.length()==0)
{
ans.put(rp.vname,-1);
continue;
}
ans.put(rp.vname,rp.cost);
for(int nbr: vtces.get(rp.vname).nbrs.keySet())
{
if(map.containsKey(nbr))
{
DijkstraPair nv=map.get(nbr);
int oc=nv.cost;
int nc=rp.cost+vtces.get(rp.vname).nbrs.get(nbr);
if(nc<oc)
{
nv.psf=rp.psf+nv.vname;
nv.cost=nc;
heap.updatepriority(nv);
}
}
}
}
return ans;
}
public static void main(String args[]) {
Scanner kb=new Scanner(System.in);
int t=kb.nextInt();
while(t-->0)
{
int n=kb.nextInt();
int m=kb.nextInt();
Graph g=new Graph();
while(m-->0)
{
int x=kb.nextInt();
int y=kb.nextInt();
int cost=kb.nextInt();
g.addEdge(x,y,cost);
}
int src=kb.nextInt();
HashMap<Integer,Integer> map1=g.dijkstra(src);
Set<Map.Entry<Integer,Integer>> entries=map1.entrySet();
for(Map.Entry<Integer,Integer> entry: entries)
{
if(entry.getKey()!=src)
System.out.print(entry.getValue()+" ");
}
}
}
}