Getting Wrong Answer during submission

#1

import java.util.*;

public class Main
{
public static void main(String [] args)
{
Scanner scn = new Scanner(System.in);
int T = scn.nextInt();

    while(T-- != 0)
    {
     
        //no. of nodes
        int n = scn.nextInt();
        
        //no. of edges
        int m = scn.nextInt();
        
        //undirectd weighted graph
        HashMap <Integer, HashMap <Integer, Integer>> graph = new HashMap <> ();
        
        
        for(int i = 1; i<=n; i++)
            graph.put(i, new HashMap <Integer, Integer> ());
            
        for(int i = 1; i<=m ; i++)
        {
            int x = scn.nextInt();
            int y = scn.nextInt();
            int cost = scn.nextInt();
            
            graph.get(x).put(y, cost);
            graph.get(y).put(x, cost);
        }
        
        //source
        int src = scn.nextInt();
        
        
        dijkstraAlgo(graph, n, src);
        System.out.println();
    }
}



public static class Pair
{
    //vertex name
    int vname;
    
    //min. distance or cost 
    //till that vertex
    int cost;
    
    Pair(int vname, int cost)
    {
        this.vname = vname;
        this.cost = cost;
    }
}



public static void dijkstraAlgo(HashMap <Integer, HashMap <Integer, Integer>> graph, int n, int src)
{
    HashMap <Integer, Integer> finalAns = new HashMap <> ();
    
    HashMap <Integer, Pair> map = new HashMap <> ();
    
    PriorityQueue <Pair> pq = new PriorityQueue<> ((n1,n2) -> n1.cost - n2.cost);

    
    
    for(int i = 1; i<=n; i++)
    {
        Pair p = new Pair(i,Integer.MAX_VALUE);
        
        if(i == src)
        {
            p.cost = 0;
        }
        
        pq.add(p);
        
        map.put(i,p);
        
    }
    
   
    
    
    while(!pq.isEmpty())
    {
        //removed pair
        Pair rp = pq.remove();
        
        finalAns.put(rp.vname,rp.cost);
        
        
        for(int nbr : graph.get(rp.vname).keySet())
        {
            
            if(finalAns.containsKey(nbr))
                continue;
            
            
            Pair gp = map.get(nbr);
            
            //old cost
            int oc = gp.cost;
            
            
            //new cost
            int nc = rp.cost + graph.get(rp.vname).get(gp.vname);
            
            if(nc < oc)
            {
                gp.cost = nc;
				pq.remove(gp);
                pq.add(gp);
                
                
            }
            
            
        }
        
 
        
    }
       
        
        for(int i = 1; i<=n; i++)
        {
            if(i == src)
                continue;
            
            if(finalAns.get(i) == Integer.MAX_VALUE)
                System.out.print("-1 ");
            else
                System.out.print(finalAns.get(i) + " ");
        }
        
    
    
    
    
    
    
    
}

}

#2

what kind of instant doubt support is this? plzzzz reply fast!!!

#3

Maintain 2 arrays distance and visited (boolean) of size n + 1. Put all values in distance as Integer.Max_Value. After that put distance[src] as 0. Now make a priority queue. To the heap add a node src and cost = 0.

Start a while loop until the heap is empty. Get the first node in heap. Now if its already visited continue. Else get neighbours of current node. Update value only if not visited and new val < old val. Insert node in the heap (duplicated can be present).

#4

You can also test your code for the test below:
Input:
1
20 54
1 7 45
2 14 15
3 7 29
4 1 48
5 1 66
6 7 17
7 14 15
8 14 43
9 1 27
10 1 33
11 14 64
12 14 27
13 7 66
14 7 54
15 14 56
16 7 21
17 1 20
18 1 34
19 7 52
20 14 14
9 14 9
15 1 39
12 1 24
9 1 16
1 2 33
18 1 46
9 1 28
15 14 3
12 1 27
1 2 5
15 1 34
1 2 28
9 7 16
3 7 23
9 7 21
9 14 19
3 1 20
3 1 5
12 14 19
3 14 2
12 1 46
3 14 5
9 14 44
6 14 26
9 14 16
9 14 34
6 7 42
3 14 27
1 7 9
1 7 41
15 14 19
12 7 13
3 7 10
1 7 2
17
Correct output: 20 25 25 68 86 39 22 70 36 53 91 35 88 27 30 43 54 74 41
your :20 48 25 68 86 64 22 95 43 53 116 35 88 52 54 43 66 74 66

#5

If you look above, There are multiple 1 7 9 1 7 41 1 7 2

#6

why is that so ? Two vertices with 3 different costs