10246 - Asterix and Obelix

[serur]

Well, shortest path Floyd algo also works - only for some unknown reason you need to use it twice (yes, don't be surprised). For when used once it gives WA, twice - AC!

[nymo]

Thanks serur, I actually implemented dijkstra's shortest path algo. with binary heap and tried to get ACC to check the correctness of my implementation. This implementation gives ACC for 423... however, it is WA here , so, I am quite puzzled about the correctness of my implementation of dijkstra or is it something with the logic for this specific problem(data structure or some stuff like that) : 10246..... okay, I will sometime try with FW... Thanks for your help. It is really appreciated

[Jan]

For this

Input:

Code: Select all

9 9 2 
1 10 5 2 3 1 1 20 1 
1 2 1 
2 3 1 
3 6 1 
1 4 2 
4 5 2 
5 6 2 
6 7 1 
7 8 1 
8 9 1 
1 6 
1 9 
0 0 0

Output:

Code: Select all

Case #1
9
26

The second case returns 26. Because from 1 to 9 the path is

Code: Select all

Path   Cost
1 2      1
2 3      1
3 6      1
6 7      1
7 8      1
8 9      1
And among these, the costliest city is 9 and the cost is 20
So, total cost is 26.

Hope it helps.

[emiraga]

Well, shortest path Floyd algo also works - only for some unknown reason you need to use it twice (yes, don't be surprised). For when used once it gives WA, twice - AC!

Does anyone have idea why do we need to run Floyd Warshall twice on the same matrix? I also get WA for only one run.

Relaxation condition:

Code: Select all

cost[i][j] + large[i][j] > cost[i][k] + cost[k][j] + max ( large[i][k], large[k][j] )

[iggy]

A simpler example where single Floyd-Warshall is too greedy: it discards shorter path over city 3 because it's expensive to party there, even though a more expensive city (5) is inevitably encountered later.

Code: Select all

5 5 1
10 10 20 10 30
1 2 2
1 3 1
2 4 2
3 4 1
4 5 5
1 5

I'm guessing running the algorithm the second time helps because we then know the most expensive (inevitable) city in every path (?). I'm not convinced you can't come up with a counter-example that would fail even if F-W is run twice..

Would a proper F-W based solution have to store every path with it's max_feast between each pair of cities?

[hasib_bd]

Hi,
I've checked with many sets of inputs from file and it works perfectly but getting WA from OJ. Could there be any tricky input which i might be missing?

[hasib_bd]

My code is below. Always getting WA. The code may seem hasty. Please somebody help me to point out the error. Please help.

Code: Select all

deleted

[plamplam]

Some test cases

Code: Select all

8 25 5
0 3 48 7 48 2 24 22
5 7 17
5 4 30
3 7 2
6 5 31
1 3 25
5 8 33
1 8 34
7 8 0
2 7 31
6 3 40
4 3 33
2 5 49
1 5 48
4 2 31
7 6 34
3 2 25
8 6 7
7 1 45
8 2 38
1 2 16
7 4 24
1 6 18
6 2 25
3 8 8
1 4 7
7 2
5 2
3 5
3 4
1 4


30 400 50
5 33 36 49 21 0 49 37 18 37 28 43 11 17 5 45 16 31 22 36 31 15 13 46 24 45 24 48 47 9 
19 21 6
5 7 47
20 12 39
23 19 46
5 11 16
7 26 5
24 1 6
10 2 29
22 18 19
10 18 26
1 22 10
24 20 41
27 16 18
12 16 9
7 13 37
11 6 27
29 20 36
28 5 24
25 12 11
14 11 3
20 10 32
6 18 13
8 3 0
29 28 30
23 6 45
8 27 5
4 28 17
12 30 19
27 28 32
10 11 19
6 25 24
27 30 43
1 29 35
6 7 36
5 30 1
23 16 41
17 22 42
2 8 20
24 13 16
21 5 3
5 19 47
22 8 2
26 10 27
6 15 36
24 4 43
15 29 47
21 14 10
1 10 37
5 17 36
28 3 45
19 16 33
28 21 26
9 25 24
17 25 20
15 24 9
30 20 28
18 28 44
17 26 18
23 4 46
3 22 40
2 9 14
3 26 24
9 30 29
19 27 12
16 14 6
2 6 22
18 12 20
23 22 29
17 1 43
20 15 9
3 19 36
5 18 19
2 15 42
5 2 6
20 28 32
17 4 4
9 5 35
30 25 8
13 25 20
19 9 3
18 15 15
26 25 10
5 22 21
20 27 37
14 12 21
5 29 6
22 27 37
17 24 33
20 5 30
1 26 10
27 2 47
3 11 29
21 23 7
4 11 33
21 30 33
25 27 47
9 28 43
12 2 48
5 27 45
30 28 26
20 7 4
20 1 1
27 24 1
23 2 25
13 29 45
20 16 32
2 3 39
17 11 30
29 23 32
17 6 5
6 8 3
1 7 32
8 23 0
1 6 9
3 20 26
6 14 8
28 25 26
26 16 7
18 20 27
2 7 15
23 1 36
26 14 47
17 13 9
30 18 11
4 19 20
18 23 14
6 20 37
8 26 20
7 11 19
19 2 20
6 24 3
21 6 45
2 1 0
27 23 26
9 26 8
29 11 42
19 6 33
29 6 40
13 9 36
28 1 5
8 1 19
19 25 19
30 15 10
10 12 4
12 7 44
12 24 0
28 16 21
21 20 17
13 19 37
1 19 40
9 23 15
15 17 35
4 30 30
14 9 42
26 2 39
2 4 44
22 14 13
19 14 15
1 25 19
8 28 33
3 13 35
10 6 45
12 4 23
10 8 13
25 3 48
13 18 49
16 17 22
22 7 24
16 21 34
21 3 28
6 12 41
12 15 46
19 8 34
9 24 20
16 7 3
29 4 46
9 21 49
24 23 24
21 24 46
19 10 33
25 24 3
23 25 18
26 12 11
24 2 38
15 21 44
12 17 42
28 13 36
29 26 8
2 20 22
15 4 5
22 10 16
11 20 11
15 27 23
4 7 26
1 15 9
30 24 44
24 8 17
6 9 27
15 10 44
13 15 36
19 15 22
3 10 33
7 10 18
11 15 35
21 12 31
27 17 22
7 9 2
17 10 45
9 22 45
18 1 13
7 23 31
3 24 20
27 4 10
24 5 23
12 29 27
12 27 37
11 23 4
5 6 30
13 10 15
15 3 44
26 20 41
15 16 18
30 17 14
10 28 28
23 30 46
8 7 25
7 15 42
27 18 44
19 12 16
24 18 26
8 16 35
30 14 20
29 24 46
8 30 1
18 8 9
6 28 35
13 11 30
5 12 18
5 10 46
2 14 8
13 22 33
16 24 34
17 29 21
16 22 22
13 23 44
7 3 35
3 4 27
19 28 22
20 23 26
13 2 27
7 19 6
25 16 28
30 13 26
18 19 28
26 22 8
9 20 5
11 27 24
1 9 30
18 9 7
13 12 18
9 15 36
27 29 3
12 9 45
4 5 11
27 7 44
28 2 23
23 28 45
27 10 27
21 18 8
19 11 49
27 1 10
30 2 39
3 5 47
29 2 25
4 8 39
4 10 44
3 1 22
22 15 1
9 16 48
8 21 12
30 6 27
16 11 28
18 3 49
17 7 10
21 29 24
25 21 3
4 9 20
28 22 4
30 29 40
17 9 28
17 28 36
25 5 18
16 30 12
25 4 18
6 4 7
24 11 48
16 5 1
20 17 32
7 25 43
10 14 7
14 15 33
14 7 26
11 2 42
17 19 20
10 29 45
24 28 49
6 27 26
16 29 40
1 5 26
20 22 19
19 24 29
4 26 26
11 12 4
29 14 22
18 4 31
22 19 21
14 5 12
14 24 48
1 14 2
8 25 12
3 9 32
10 9 32
23 17 48
3 23 46
20 25 34
13 16 21
3 12 44
22 30 32
10 21 17
26 11 42
28 7 4
8 17 16
20 8 46
4 14 31
26 27 34
28 14 44
3 17 28
18 17 12
29 3 19
25 11 20
8 29 20
10 23 40
13 8 47
4 16 3
7 21 7
1 30 38
12 22 28
18 2 15
26 18 34
26 19 46
15 23 29
25 29 49
26 15 27
9 27 15
13 6 12
13 26 25
14 25 11
13 5 6
16 3 21
11 18 25
14 3 9
17 14 26
18 7 12
16 6 30
13 20 15
11 22 13
1 12 34
22 25 26
28 11 32
21 1 6
14 13 3
4 21 27
14 23 30
27 14 44
1 13 48
8 15 28
5 23 20
30 19 17
4 20 34
30 3 29
22 24 16
2 17 15
11 8 17
8 14 16
6 3 47
2 16 9
15 28 17
5 8 28
21 13 48
20 14 28
2 21 9
26 6 14
16 1 47
27 3 22
25 18 45
11 1 32
23 26 10
29 19 35
4 13 47
16 18 47
1 13
3 10
9 27
28 8
24 23
16 29
9 17
21 4
29 23
13 3
8 17
21 24
3 20
10 3
26 4
2 7
4 15
29 17
2 17
15 11
30 1
11 1
12 14
17 5
15 1
17 27
15 5
15 19
18 16
3 17
24 21
21 26
15 21
7 26
10 29
30 17
15 8
16 10
8 9
12 16
5 26
13 2
23 3
21 20
24 25
6 30
17 27
5 19
4 5
25 27

0 0 0

Code: Select all

Case #1
55
92
67
74
14

Case #2
22
50
39
54
52
54
45
56
55
45
45
52
46
50
59
54
54
59
47
42
28
33
50
36
14
46
32
44
57
45
52
56
45
54
55
30
40
58
51
54
53
38
37
43
49
35
46
40
53
47

[rumman]

Can any one explain me the sample 1st test case of this problem?Why the answer for "1 5" is 45?

[rumman]

Are you asking about the correct problem number rumman?

I mean
/*
7 8 5
2 3 5 15 4 4 6
1 2 20
1 4 20
1 5 50
2 3 10
3 4 10
3 5 10
4 5 15
6 7 10
1 5
1 6
5 1
3 1
6 7
*/
in this test case why the answer is 45 for query "1 5".
But I figure it out and solved it. BTW thanks for your response.

[lighted]

Some test cases

Code: Select all

8 25 5
0 3 48 7 48 2 24 22
5 7 17
5 4 30
3 7 2
6 5 31
1 3 25
5 8 33
1 8 34
7 8 0
2 7 31
6 3 40
4 3 33
2 5 49
1 5 48
4 2 31
7 6 34
3 2 25
8 6 7
7 1 45
8 2 38
1 2 16
7 4 24
1 6 18
6 2 25
3 8 8
1 4 7
7 2
5 2
3 5
3 4
1 4


30 400 50
5 33 36 49 21 0 49 37 18 37 28 43 11 17 5 45 16 31 22 36 31 15 13 46 24 45 24 48 47 9 
19 21 6
5 7 47
20 12 39
23 19 46
5 11 16
7 26 5
24 1 6
10 2 29
22 18 19
10 18 26
1 22 10
24 20 41
27 16 18
12 16 9
7 13 37
11 6 27
29 20 36
28 5 24
25 12 11
14 11 3
20 10 32
6 18 13
8 3 0
29 28 30
23 6 45
8 27 5
4 28 17
12 30 19
27 28 32
10 11 19
6 25 24
27 30 43
1 29 35
6 7 36
5 30 1
23 16 41
17 22 42
2 8 20
24 13 16
21 5 3
5 19 47
22 8 2
26 10 27
6 15 36
24 4 43
15 29 47
21 14 10
1 10 37
5 17 36
28 3 45
19 16 33
28 21 26
9 25 24
17 25 20
15 24 9
30 20 28
18 28 44
17 26 18
23 4 46
3 22 40
2 9 14
3 26 24
9 30 29
19 27 12
16 14 6
2 6 22
18 12 20
23 22 29
17 1 43
20 15 9
3 19 36
5 18 19
2 15 42
5 2 6
20 28 32
17 4 4
9 5 35
30 25 8
13 25 20
19 9 3
18 15 15
26 25 10
5 22 21
20 27 37
14 12 21
5 29 6
22 27 37
17 24 33
20 5 30
1 26 10
27 2 47
3 11 29
21 23 7
4 11 33
21 30 33
25 27 47
9 28 43
12 2 48
5 27 45
30 28 26
20 7 4
20 1 1
27 24 1
23 2 25
13 29 45
20 16 32
2 3 39
17 11 30
29 23 32
17 6 5
6 8 3
1 7 32
8 23 0
1 6 9
3 20 26
6 14 8
28 25 26
26 16 7
18 20 27
2 7 15
23 1 36
26 14 47
17 13 9
30 18 11
4 19 20
18 23 14
6 20 37
8 26 20
7 11 19
19 2 20
6 24 3
21 6 45
2 1 0
27 23 26
9 26 8
29 11 42
19 6 33
29 6 40
13 9 36
28 1 5
8 1 19
19 25 19
30 15 10
10 12 4
12 7 44
12 24 0
28 16 21
21 20 17
13 19 37
1 19 40
9 23 15
15 17 35
4 30 30
14 9 42
26 2 39
2 4 44
22 14 13
19 14 15
1 25 19
8 28 33
3 13 35
10 6 45
12 4 23
10 8 13
25 3 48
13 18 49
16 17 22
22 7 24
16 21 34
21 3 28
6 12 41
12 15 46
19 8 34
9 24 20
16 7 3
29 4 46
9 21 49
24 23 24
21 24 46
19 10 33
25 24 3
23 25 18
26 12 11
24 2 38
15 21 44
12 17 42
28 13 36
29 26 8
2 20 22
15 4 5
22 10 16
11 20 11
15 27 23
4 7 26
1 15 9
30 24 44
24 8 17
6 9 27
15 10 44
13 15 36
19 15 22
3 10 33
7 10 18
11 15 35
21 12 31
27 17 22
7 9 2
17 10 45
9 22 45
18 1 13
7 23 31
3 24 20
27 4 10
24 5 23
12 29 27
12 27 37
11 23 4
5 6 30
13 10 15
15 3 44
26 20 41
15 16 18
30 17 14
10 28 28
23 30 46
8 7 25
7 15 42
27 18 44
19 12 16
24 18 26
8 16 35
30 14 20
29 24 46
8 30 1
18 8 9
6 28 35
13 11 30
5 12 18
5 10 46
2 14 8
13 22 33
16 24 34
17 29 21
16 22 22
13 23 44
7 3 35
3 4 27
19 28 22
20 23 26
13 2 27
7 19 6
25 16 28
30 13 26
18 19 28
26 22 8
9 20 5
11 27 24
1 9 30
18 9 7
13 12 18
9 15 36
27 29 3
12 9 45
4 5 11
27 7 44
28 2 23
23 28 45
27 10 27
21 18 8
19 11 49
27 1 10
30 2 39
3 5 47
29 2 25
4 8 39
4 10 44
3 1 22
22 15 1
9 16 48
8 21 12
30 6 27
16 11 28
18 3 49
17 7 10
21 29 24
25 21 3
4 9 20
28 22 4
30 29 40
17 9 28
17 28 36
25 5 18
16 30 12
25 4 18
6 4 7
24 11 48
16 5 1
20 17 32
7 25 43
10 14 7
14 15 33
14 7 26
11 2 42
17 19 20
10 29 45
24 28 49
6 27 26
16 29 40
1 5 26
20 22 19
19 24 29
4 26 26
11 12 4
29 14 22
18 4 31
22 19 21
14 5 12
14 24 48
1 14 2
8 25 12
3 9 32
10 9 32
23 17 48
3 23 46
20 25 34
13 16 21
3 12 44
22 30 32
10 21 17
26 11 42
28 7 4
8 17 16
20 8 46
4 14 31
26 27 34
28 14 44
3 17 28
18 17 12
29 3 19
25 11 20
8 29 20
10 23 40
13 8 47
4 16 3
7 21 7
1 30 38
12 22 28
18 2 15
26 18 34
26 19 46
15 23 29
25 29 49
26 15 27
9 27 15
13 6 12
13 26 25
14 25 11
13 5 6
16 3 21
11 18 25
14 3 9
17 14 26
18 7 12
16 6 30
13 20 15
11 22 13
1 12 34
22 25 26
28 11 32
21 1 6
14 13 3
4 21 27
14 23 30
27 14 44
1 13 48
8 15 28
5 23 20
30 19 17
4 20 34
30 3 29
22 24 16
2 17 15
11 8 17
8 14 16
6 3 47
2 16 9
15 28 17
5 8 28
21 13 48
20 14 28
2 21 9
26 6 14
16 1 47
27 3 22
25 18 45
11 1 32
23 26 10
29 19 35
4 13 47
16 18 47
1 13
3 10
9 27
28 8
24 23
16 29
9 17
21 4
29 23
13 3
8 17
21 24
3 20
10 3
26 4
2 7
4 15
29 17
2 17
15 11
30 1
11 1
12 14
17 5
15 1
17 27
15 5
15 19
18 16
3 17
24 21
21 26
15 21
7 26
10 29
30 17
15 8
16 10
8 9
12 16
5 26
13 2
23 3
21 20
24 25
6 30
17 27
5 19
4 5
25 27

0 0 0

Code: Select all

Case #1
55
92
67
74
14

Case #2
22
50
39
54
52
54
45
56
55
45
45
52
46
50
59
54
54
59
47
42
28
33
50
36
14
46
32
44
57
45
52
56
45
54
55
30
40
58
51
54
53
38
37
43
49
35
46
40
53
47

For test above my program gives same output except last one.
It is a quite big test to check it manually. Can somebody check if the above output for last query is correct?

Code: Select all

Case #1
55
92
67
74
14

Case #2
22
50
39
54
52
54
45
56
55
45
45
52
46
50
59
54
54
59
47
42
28
33
50
36
14
46
32
44
57
45
52
56
45
54
55
30
40
58
51
54
53
38
37
43
49
35
46
40
53
50

[brianfry713]

Yes the last query is correct, you can get from 25 to 27 with a cost of 23 and a feast of 24.
25->14 cost 11
14->1 cost 2
1->27 cost 10

[lighted]

I fixed a bug and it is now work for input test above, but i get WA.
I run dijkstra's algo two times.

1) dijkstra's algo. Every time it finds node with minimal path and improve other nodes

if pathCost[min] + edge[min] + max(feastCost[min], feast) < pathCost + feastCost


2) dijkstra's algo. Every time it finds node with minimal sum of path and feast and improve other nodes

if pathCost[min] + edge[min] + max(feastCost[min], feast) < pathCost + feastCost

I run second dijkstra's algo to improve results with nodes which have cheap feast value.

Please tell where is my mistake
Thanks in advance

Code: Select all

removed, after acc..

[brianfry713]

Try using Floyd-Warshall's algorithm twice.

[lighted]

Thanks!
I got acc by using Floyd-Warshall's algorithm twice.
But i didn't understand why Dijkstra's algorithm version was WA.
Anyway i solved this problem. Thansks again!