In short question says that you have N bus stops and K bus routes. Every bus routes is linked to two bus stops. Each route has some cost of travelling. It says one person visit any one bus stop(N-1 bus stop require N-1 person). Task of person is to start from bus stop 1 and visit his bus stop stay there for complete day and come back. One complete journey from bus stop 1 -> bust stop x and return path need to pay some cost. This cost is payable by one head who appointed these person. So what is the minimum cost is to be paid by this head.


The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case begins with a line containing exactly two integers P and Q, 1 <= P,Q <= 1000000. P is the number of stops including CCS and Q the number of bus lines. Then there are Q lines, each describing one bus line. Each of the lines contains exactly three numbers - the originating stop, the destination stop and the price. The CCS is designated by number 1. Prices are positive integers the sum of which is smaller than 1000000000. You can also assume it is always possible to get from any stop to any other stop

Test Case

2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

I am solving the SPOJ question INCARDS. I am solving this problem using Dijkstra algorithm. According to algorithm I used, I run Dijkstra on directed and reverse of the same directed graph. And at the end I add up the cost array I get from the both.

//Complete this code or write your own from scratch
import java.util.*;
import java.io.*;
import java.math.*;

class Solution{

    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;
        private void fillBuffer() throws IOException
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        public String readLine() throws IOException 
            byte[] buf = new byte[128]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
                if (c == '\n') 
                buf[cnt++] = (byte) c; 
            return new String(buf, 0, cnt); 
        private byte read() throws IOException
            if (bufferPointer == bytesRead)
            return buffer[bufferPointer++];
        public int nextInt() throws IOException
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;

    static int[][] arr;
    static int[][] rev;
    public static void main(String []argh) throws Exception{
        Reader br = new Reader();
        int t= br.nextInt();
        for(int aa=0; aa<t; aa++){
            int p= br.nextInt();
            int q= br.nextInt();
            arr = new int[p+1][p+1];
            rev = new int[p+1][p+1];
            for(int qq= 1; qq<=q; qq++){
                int o= br.nextInt();
                int d= br.nextInt();
                int pp= br.nextInt();
                arr[o][d]= pp;
                rev[d][o]= pp;
            int[] data= dijkstra(arr, p);
            int[] data1= dijkstra(rev, p);
            int sum =0;
            for(int i=2; i<=p; i++){
                sum += data[i] + data1[i];

    static Queue<Data> integerPQ;
    static int[] currPath;
    static int[] distMap;
    static int[] visited;
    private static int[] dijkstra(int[][] arr, int p) {
        currPath = new int[p+1];
        distMap = new int[p+1];
        visited = new int[p+1];
        integerPQ = new PriorityQueue<>();
        for(int zz=1; zz<=p; zz++) distMap[zz]= Integer.MAX_VALUE;
        integerPQ.add(new Data(1, 0));
        while(integerPQ.peek() != null) {
            Data dd= integerPQ.poll();
            if(distMap[dd.ind] > dd.cost) {
                distMap[dd.ind] = dd.cost;
                for(int kk= 1; kk<=p; kk++) {
                    if(arr[dd.ind][kk] != 0) {
                        int totalPrice= arr[dd.ind][kk] + dd.cost;
                        if(distMap[kk] > totalPrice && visited[kk] == 0) {
                            integerPQ.add(new Data(kk, totalPrice));
                visited[dd.ind] = 1;
        return distMap;

    private static class Data implements Comparable<Data>{
        int ind;
        int cost;

        public Data(int ind, int cost){
            this.ind= ind;
            this.cost= cost;

        public int compareTo(Data d){
            if(d.cost > this.cost)return -1;
            else if(d.cost < this.cost) return 1;
            else {
                if(d.ind > this.ind) return -1;
                else if(d.ind < this.ind) return 1;
                else return 0;



Now coming to time complexity: it has TC \$O(V+E) \rightarrow O(N)\$ considering. I am getting Time Limit Exceeded when I submit. I tried a lot to figure out the issue. But I could find none. It looks each node is running at most only once. I don't know where it is consuming time, even I am using Fast I/O.

Can someone point out issues prevailing in my solution so that I can learn new facts about optimizing codes and algorithms?

  • \$\begingroup\$ Welcome to Code Review! Could you please edit to add a short summary of the problem statement? You can keep the link as a reference, but your question does need to be complete even if the linked material isn't accessible. Thanks. \$\endgroup\$ Sep 10, 2018 at 7:40

1 Answer 1


Consider using other(sparse) graph representation. You are getting O(V*V) since you check for all possible connections (arr[dd.ind][*]), even when actual edge count is low.

  • \$\begingroup\$ Adjacency list did solved y issue. \$\endgroup\$
    – Ladoo
    Sep 13, 2018 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.