The Parking Slot | Editorial by aksingh007

Use the efficient dijkstra's algorithm to solve this prolem.

```
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 implements Comparable<Edge>{
	int u,v,weight;
	Edge(int x,int y,int w){u=x;v=y;weight=w;}
	public int compareTo(Edge obj){
		return this.weight-obj.weight;
	}
}

class Pair implements Comparable<Pair>{
    int node,cap;long cost;
    Pair(long c,int n,int cp){cost=c;node=n;cap=cp;}
    public int compareTo(Pair obj){
        return (int)(this.cost-obj.cost);
    }
}

class Distance implements Comparable<Distance>{
	int vertex;long distance;
	Distance(int v,long d){vertex=v;distance=d;}
 	public int compareTo(Distance obj){
 		return (int)(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 dijkstra(int src,long pathCost[]){
		boolean visited[]=new boolean[N];
		PriorityQueue<Distance> pq=new PriorityQueue<Distance>();
		pq.offer(new Distance(src,0L));
		while(!pq.isEmpty()){
			Distance top=pq.poll();
			int cur=top.vertex;
			long 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]));
			}
		}
	}
	void print(){
		for(int i=1;i<N-1;i++){
			System.out.print(i+":");
			for(Node nd:adj[i]){
				System.out.print("("+nd.next+","+nd.weight+")");
			}
			System.out.println();
		}
	}
}
	
class GraphAlgos{
	public static void main(String args[]) throws Exception{
		Reader sc=new Reader();
		long inf=10000000000000000L;
		int n=sc.nextInt();
		int m=sc.nextInt();
		int f=sc.nextInt();
		int capacity[]=new int[n+1];
		for(int i=1;i<=n;capacity[i++]=sc.nextInt());
		Graph graph=new Graph(n+1);
		for(int i=0;i<m;i++)
			graph.push_edge(sc.nextInt(),sc.nextInt(),sc.nextInt());
			 
		int K=sc.nextInt();
		long pathCost[]=new long[n+2];
		graph.dijkstra(1,pathCost);
	
	//	Arrays.sort(pathCost);
		//System.out.println(Arrays.toString(pathCost));
		long res[]=new long[K];
		Arrays.fill(res,-1);
		Pair arr[]=new Pair[n];
		for(int i=1;i<=n;i++)
		    arr[i-1]=new Pair(pathCost[i],i,capacity[i]);
		Arrays.sort(arr);
		int pos=0;
		//ArrayList<Integer> fare=new ArrayList<Integer>();
		for(int i=0;i<n;i++){
		    Pair p=arr[i];
		   // System.out.println(p.cost+" "+p.node+" "+p.cap);
		    while(p.cap>0 && K>0){
		    
		     res[pos++]=(p.cost+f);
		     p.cap--;K--;
		    }
		    if(K<0) break;
		}
// 		for(int i=0;i<res.length;i++)
// 		System.out.print(res[i]+" ");
		StringBuilder sb = new StringBuilder();

for(int i=0;i<res.length;i++)
		 { sb.append(res[i]).append(" ");}
        String printMe = sb.toString(); 
        System.out.println(printMe);
		
	}
	
	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[1364]; // 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;
        }
 
 
        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();
        }
    }
}

```

The Parking Slot | Editorial by aksingh007

Download submission

All caught up!

View submission

Is your resume even shortlisted?