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?
