Ignore the previous code. I’m sure this code is correct but I’m getting WA. I think my answer format is incorrect. Can you please check
Https://ide.codingblocks.com/s/251251
Maintain 2 arrays distance and visited (boolean) of size n + 1. Put all values in distance as Integer.Max_Value. After that put distance[src] as 0. Now make a priority queue. To the heap add a node src and cost = 0.
Start a while loop until the heap is empty. Get the first node in heap. Now if its already visited continue. Else get neighbours of current node. Update value only if not visited and new val < old val. Insert node in the heap (duplicated can be present).
You can also test your code for the test below:
Input:
1
20 54
1 7 45
2 14 15
3 7 29
4 1 48
5 1 66
6 7 17
7 14 15
8 14 43
9 1 27
10 1 33
11 14 64
12 14 27
13 7 66
14 7 54
15 14 56
16 7 21
17 1 20
18 1 34
19 7 52
20 14 14
9 14 9
15 1 39
12 1 24
9 1 16
1 2 33
18 1 46
9 1 28
15 14 3
12 1 27
1 2 5
15 1 34
1 2 28
9 7 16
3 7 23
9 7 21
9 14 19
3 1 20
3 1 5
12 14 19
3 14 2
12 1 46
3 14 5
9 14 44
6 14 26
9 14 16
9 14 34
6 7 42
3 14 27
1 7 9
1 7 41
15 14 19
12 7 13
3 7 10
1 7 2
17
Correct output: 20 25 25 68 86 39 22 70 36 53 91 35 88 27 30 43 54 74 41
Your output: 20 53 40 68 86 141 69 158 85 53 179 82 135 115 59 90 54 121 129