IITKESO207A_4P_1 - Single Source Shortest Path
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 11031 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-15 06:40:10
@age: Check overflow for values of distances. If integer overflow occurs, distances could become negative. |
|
poopybutthole:
2017-11-14 19:35:08
Why are your run cases so weird? Last edit: 2017-11-14 19:35:17 |
|
age:
2017-11-14 19:00:21
@Programming Club, IITK
|
|
Programming Club, IITK:
2017-11-14 15:24:48
@age: Nope. In that case you will see SIGSEGV or other runtime error. WA is WA. If 13 cases are passing and not the other 2, look for overflow related errors. Put some assertions (use assert from assert.h) in your code, and try to verify that values are within particular bounds[and not overflowing]. You shall see WA turning into runtime error, if assertion fails. Last edit: 2017-11-14 15:25:12 |
|
age:
2017-11-14 14:43:25
Can a test case give WA if the size is going out-of-bounds, or will some other error will show up? The code is working for all but 2 test cases. |
|
Programming Club, IITK:
2017-11-12 19:57:11
@subham todi: All test cases are correct and follow the given constraints.
|
|
subham todi:
2017-11-11 17:38:32
Do use long long int even for these parameter "N Source D C_1 C_2 D_1 D_2 W_1 W_2 W_3 ". Although the constraint suggest they are in range of int, but u get WA using int.
|
|
nikhilbl:
2017-11-10 17:35:53
@ashutoshs25 Thanks. Your comment saved a lot of time. :) I just changed every int to long long int and got 100 from 0. :) |
|
Programming Club, IITK:
2017-11-09 05:19:11
@nihir16: No. We won't provide new test cases. |
Added by: | Programming Club, IITK |
Date: | 2017-11-01 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |