import java.util.*;
public class Main{
static class Pair implements Comparable<Pair>{
int vtx;
int cost;
Pair(int n,int c){
this.vtx = n;
this.cost = c;
}
public int compareTo(Pair obj){
return this.cost- obj.cost;
}
}
public static void main(String[] args){
Scanner scn = new Scanner(System.in);
int N = scn.nextInt();
int M = scn.nextInt();
ArrayList<Pair>[] graph = new ArrayList[N];
for(int i=0;i<graph.length;i++) graph[i]=new ArrayList();
for(int i=0;i<N;i++){
int src = scn.nextInt();
int dest = scn.nextInt();
graph[src-1].add(new Pair(dest-1,0));
graph[dest-1].add(new Pair(src-1,1));
}
System.out.println( dijkstra(graph,0,N-1,new boolean[N]) );
}
public static int dijkstra(ArrayList<Pair>[] graph,int S,int D,boolean[] visited){
Deque<Pair> que = new ArrayDeque();
que.add(new Pair(S,0));
while(que.size()>0){
Pair ele = que.pollFirst();
int vtx = ele.vtx;
int cost = ele.cost;
if(vtx==D) return cost;
if(!visited[vtx]){
//mark
visited[vtx]=true;
for(int i=0;i<graph[vtx].size();i++){
Pair nbrP = graph[vtx].get(i);
int nbr = nbrP.vtx;
int nbrcost = nbrP.cost;
// System.out.println(vtx+"->"+nbr+" :"+nbrcost);
if(visited[nbr])continue;
if(que.size()>0 && que.peek().cost>= nbrcost+cost){
que.addFirst(new Pair(nbr,nbrcost+cost));
}else{
que.addLast(new Pair(nbr, nbrcost+cost));
}
}
}
}
return -1;
}
}
Why does my approach give runtime error
can anyone please explain?
Question Link - > CodeChef: Practical coding for everyone