IITKESO207A_4P_1 - Single Source Shortest Path

no tags 

In this problem, you will solve the single source shortest path problem for a given directed weighted graph with no negative weight edges using Dijkstra’s Algorithm.

The input will consist of a few numbers N, Source, D, C_1 , C_2 , D_1, D_2,  W_1 , W_2, W_3.

N = Number of nodes in the graph (numbered 1,2...N )

D = Max outdegree of any node

Source = The source node (between 1 and N inclusive)

C_1, C_2, D_1, D_2, W_1, W_2, W_3 are just some constants,

You have to create the graph using the pseudo code given below:

for i = 1 to N :  //Inclusive
deg = ( i*C_2 + i*i*D_2 ) mod D
for j = 1 to deg: //Inclusive
temp_node.vertex = ( i*C_1 + j*D_1 ) mod N
temp_node.vertex += 1
temp_node.weight = ( i*W_1 + j*W_2 ) mod W_3 //Weight of edge ( i, temp_node.vertex)
adj_list [ i ].enqueue( temp_node )

You have to print the minimum cost of traversing from the source to all the vertices [1,N]

Note- 

1) Do not use Bellman Ford algorithm as it won't work here. It will give you a TLE error.

2) You are supposed to implement the priority queue yourself. You cannot use any prebuilt priority queue , (max/min) heap , map etc functions. However, you can use sort functions , queues for adjacency list etc. Please contact the SPOJ TAs if there is any doubt.

3) Make sure your program uses less than 10^6 * sizeof(long long int) memory. Creating a matrix of size N*N wont work for all the test cases.  

4) There might be self loops and multiple edges between two nodes in the graph.

5) Overall time complexity should be O((E + V)lgV), otherwise you will get TLE.

Input

Input consist of 10 space separated integers in the following format.

N Source D C_1 C_2 D_1 D_2 W_1 W_2 W_3 

Constraints

1 <= N <= 10^5
N*D <= 10^6
1 <= C_1, C_2, D_1, D_2 <= 10^3
1 <= Source <= N
0 <= W_1, W_2, W_3 <= 10^3

 

Output

Print the table of shortest path distances from the source vertex to all the vertices. This table should contain N lines. Each line should contain (space separated)  vertex-id and distance,  successively, for vertex-id = 1, 2, . . . , N. If you cannot reach vertex-id from source, print -1 for distance.

Example

Input:
8 2 5 446 192 703 336 56 75 1000

Output:
1 1103
1 1103 2 0 3 262 4 187 5 711 6 636 7 561 8 486
Input:
10 1 4 315 567 647 270 15 35 1000
Output:
1 0
2 -1
3 50
4 -1
5 385
6 -1
7 200
8 350
9 -1
10 165

hide comments
Programming Club, IITK: 2017-11-09 05:19:11

@nihir16: No. We won't provide new test cases.

nihir16: 2017-11-07 15:34:33

My code also runs for the two given test cases but for the others it's WA. Can you please add some more visible cases?

Programming Club, IITK: 2017-11-05 05:14:53

@lightstark1: You are supposed to use priority queue with normal binary heap with O((E+V)lgV). No need of fibonacci heap

lightstark1: 2017-11-04 19:13:44

Hi, do we have fibonacci heap for priority queue, cause the complexity you have given doesn't come with normal binary heap O(ElgV + VlgV)?

shree_19818: 2017-11-04 16:57:39

Getting the same problem. The code works for the given test cases but does not run for any of the test cases in the question. The error is "wrong answer". Using "%lld" isn't helping either.

ashutoshs25: 2017-11-03 19:36:55

@yvasant : I had the same problem as yours and it got corrected by using %lld in C for scanning / printing long long int type nos

Programming Club, IITK: 2017-11-03 06:48:53

@ankusht : Yes.

Programming Club, IITK: 2017-11-03 06:47:02

@yvasant : The given test cases are NOT included in the hidden test cases. Also the time limit is 1s per test case, that makes the total time 15s. WA status is never due to time limit issues.
@ ramansr: W_3 =0 will cause a divide by 0 error. None of the testcases have W_3=0.

ankusht: 2017-11-03 06:44:10

can we use <vector> and <pair> from C++ STL for implementing adjacency list?

ramansr: 2017-11-02 19:29:21

Also please tell me is there a case when W_3 = 0 ??
if yes then what should we do ??


Added by:Programming Club, IITK
Date:2017-11-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All