Shortest Path Problem | Editorial by aksingh007

An efficient implementation of dijkstra's algorithm will suffice.
NOTE: Use Fast I/O.
```
import java.util.*;
import java.io.*;
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 Edge{
	int u,v,weight;
	Edge(int x,int y,int w){u=x;v=y;weight=w;}
}
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[];
	ArrayList<Edge> edgeList;
	Graph(int n){
		N=n+1;
		adj=new ArrayList[n+1];
		for(int i=0;i<=n;adj[i++]=new ArrayList<Node>());
		edgeList=new ArrayList<Edge>();
	}
	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));
		//edgeList.add(new Edge(x,y,w));
	}
	void dfsCall(int v,boolean visited[]){
		visited[v]=true;
		for(int i=0;i<adj[v].size();i++)
			if(!visited[adj[v].get(i).next])
				dfsCall(adj[v].get(i).next,visited);
	}
	void dfs(int src){
		boolean visited[]=new boolean[N];
		dfsCall(src,visited);
	}
	int bfs(int src,int dest){
		HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
		Queue<Integer> queue=new LinkedList<Integer>();
		boolean visited[]=new boolean[N];
		queue.offer(src);
		visited[src]=true;
		hm.put(src,-1);
		while(!queue.isEmpty()){
			int cur=queue.poll();
			//if(visited[cur]) continue;
			visited[cur]=true;
			for(int i=0;i<adj[cur].size();i++){
				int next=adj[cur].get(i).next;
				if(!visited[next]){
					queue.offer(next);
					visited[next]=true;
					hm.put(next,cur);
				}
			}
		}
		if(!visited[dest]) return -1;
		ArrayList<Integer> path=new ArrayList<Integer>();
		int key=dest;
		do{
			path.add(key);
			key=hm.get(key);
		}while(key!=src);
		path.add(src);
		return path.size()-1;
	}
			
	void tSort(){
	
	}
	boolean isConnected(int src,int dest){
		boolean visited[]=new boolean[N];
		dfsCall(src,visited);
		return (visited[src] && visited[dest]);
	}
	
	void dijkstra(int src,int pathCost[]){
		boolean visited[]=new boolean[N];
		PriorityQueue<Distance> pq=new PriorityQueue<Distance>();
		pq.offer(new Distance(src,0));
		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])   //	MAY RAISE TLE !!!!!!!
					pq.offer(new Distance(nd.next,nd.weight+pathCost[cur]));
			}
		}
	}
}
	
	
class GraphAlgos{
	public static void main(String args[]) throws Exception{
		Reader sc=new Reader();
		int n=sc.nextInt();
		Graph graph=new Graph(n);
		int edges=sc.nextInt();
		for(int i=0;i<edges;i++)
			graph.push_edge(sc.nextInt(),sc.nextInt(),sc.nextInt());
		int result[]=new int[n+1];
		graph.dijkstra(1,result);
		for(int i=2;i<=n;i++)
		    if(result[i]==0)
		        System.out.print("1000000000 ");
		        else
		        System.out.print(result[i]+" ");
		  
	}
	
	static class Reader{
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader(){
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException{
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException{
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while((c=read())!=-1){
                if(c=='\n')
                    break;
                buf[cnt++]=(byte)c;
            }
            return new String(buf,0,cnt);
        }
 
        public int nextInt() throws IOException{
            int ret=0;
            byte c=read();
            while(c<=' ')
                c=read();
            boolean neg=(c=='-');
            if(neg)
                c=read();
            do{
                ret=ret*10+c-'0';
            }while((c=read())>='0' && c<='9');
            if(neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException{
            long ret=0;
            byte c=read();
            while(c<=' ')
                c=read();
            boolean neg=(c=='-');
            if(neg)
                c=read();
            do{
                ret=ret*10+c-'0';
            }
            while((c=read())>='0' && c<='9');
            if(neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException{
            double ret=0,div = 1;
            byte c=read();
            while(c<=' ')
                c=read();
            boolean neg =(c=='-');
            if(neg)
                c=read();
 
            do{
                ret=ret*10+c-'0';
            }
            while((c=read())>='0' && c<='9');
 
            if(c=='.'){
                while ((c = read()) >= '0' && c <= '9'){
                    ret+=(c-'0')/(div*=10);
                }
            }
            if(neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException{
            bytesRead = din.read(buffer,bufferPointer=0,BUFFER_SIZE);
            if (bytesRead==-1)
                buffer[0]=-1;
        }
 
        private byte read() throws IOException{
            if (bufferPointer==bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
		public void close() throws IOException{
            if (din==null)
                return;
            din.close();
        }
    }
}
 
 
Language: Java 8
```

Shortest Path Problem | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?