Dijkstra: Shortest Reach 2 | Editorial by aksingh007

To solve this problem use Single source shortest path algorithm Dijkstra. If you are new to graph theory algorithms then you can learn it [here](https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/)
```
import java.util.*;
class Node{
	int next,weight;boolean ispresent;
	Node(int x,int y,boolean p){next=x;weight=y;ispresent=p;}
	Node(int x,int y){next=x;weight=y;ispresent=true;}
}
class Distance implements Comparable<Distance>{
	int vertex,distance;
	Distance(int v,int d){vertex=v;distance=d;}
	public int compareTo(Distance obj){
		return this.distance-obj.distance;
	}
}
@SuppressWarnings("unchecked")
class Graph{
	int N;
	ArrayList<Node> adj[];
	Graph(int n){
		N=n+1;
		adj=new ArrayList[n+1];
		for(int i=0;i<=n;adj[i++]=new ArrayList<Node>());
	}
	void push_edge(int x,int y,int w){
		adj[x].add(0,new Node(y,w));
		adj[y].add(0,new Node(x,w));
	}
	void dijkstra(int src,int pathCost[]){
		boolean visited[]=new boolean[N];
		//Map<Integer,Integer> path=new Map<Integer,Integer>();
		PriorityQueue<Distance> pq=new PriorityQueue<Distance>();
		pq.offer(new Distance(src,0));
        for(int i=1;i<N;i++) if(i!=src) pq.offer(new Distance(src,Integer.MAX_VALUE));
		while(!pq.isEmpty()){
			Distance top=pq.poll();
			int cur=top.vertex;int dist=top.distance;
			if(visited[cur])
				continue;
			pathCost[cur]=dist;
			visited[cur]=true;
			for(int i=0;i<adj[cur].size();i++){
				Node nd=adj[cur].get(i);
				//if(!visited[nd.next])
					pq.offer(new Distance(nd.next,nd.weight+pathCost[cur]));
			}
			//for(Distance d:pq)
			//	System.out.println(d.vertex+" "+d.distance);
			//System.out.println("##########################################################");
	}
	}
}
	
	
class GraphAlgos{
	public static void main(String args[]){
		Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0){
		    int n=sc.nextInt();
            int mat[][]=new int[n+1][n+1];
            for(int i=0;i<=n;i++)
                for(int j=0;j<=n;j++)
                    mat[i][j]=Integer.MAX_VALUE;
		    Graph graph=new Graph(n);
		    int edges=sc.nextInt();
            for(int i=0;i<edges;i++){
                int a=sc.nextInt();
                int b=sc.nextInt();
                int w=sc.nextInt();
                if(mat[a][b]>w)
                    mat[a][b]=w;
                if(mat[b][a]>w)
                    mat[b][a]=w;
            }
           for(int i=0;i<=n;i++)
                for(int j=0;j<=n;j++)
                    if(mat[i][j]!=Integer.MAX_VALUE)
                        graph.push_edge(i,j,mat[i][j]);
		   int result[]=new int[n+1];
            int src=sc.nextInt();
		   graph.dijkstra(src,result);
		   for(int i=1;i<=n;i++)
               if(i==src) continue;
               else
               if(result[i]!=0)
		    	 System.out.print(result[i]+" ");
                else
                    System.out.print("-1 ");
	       System.out.println();
        }
        
}
}

```

Dijkstra: Shortest Reach 2 | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?