Krdytkyu

Question-

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.

Input

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 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') 

                    break; 

                buf[cnt++] = (byte) c; 

            } 

            return new String(buf, 0, cnt); 

        } 

        private byte read() throws IOException

        {

            if (bufferPointer == bytesRead)

                fillBuffer();

            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();

            do

            {

                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];

            }

            System.out.println(sum);

        }

    }



    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?

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.