# INCARDS SPOJ challenge

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{

{
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;

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

• 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. – Toby Speight Sep 10 '18 at 7:40

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.