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?

[brianfry713]

Are you asking about the correct problem number rumman?