## 10246 - Asterix and Obelix

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)
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
regards,
nymo

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

emiraga
New poster
Posts: 1
Joined: Sat Apr 19, 2008 2:22 am

### Re:

serur wrote: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
New poster
Posts: 3
Joined: Mon May 05, 2008 10:44 am

### Re: 10246 - Asterix and Obelix

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
New poster
Posts: 14
Joined: Wed Apr 30, 2008 12:39 pm

### Re: 10246 - Asterix and Obelix

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
New poster
Posts: 14
Joined: Wed Apr 30, 2008 12:39 pm

### Re: 10246 - Asterix and Obelix

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
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 10246 - Asterix and Obelix

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
``````
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

rumman
New poster
Posts: 4
Joined: Sun Nov 04, 2012 2:02 pm

### Re: 10246 - Asterix and Obelix

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

rumman
New poster
Posts: 4
Joined: Sun Nov 04, 2012 2:02 pm

### Re: 10246 - Asterix and Obelix

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10246 - Asterix and Obelix

plamplam wrote: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
``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10246 - Asterix and Obelix

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
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10246 - Asterix and Obelix

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

Code: Select all

``removed, after acc..``
Last edited by lighted on Tue Jul 15, 2014 2:21 pm, edited 1 time in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10246 - Asterix and Obelix

Try using Floyd-Warshall's algorithm twice.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10246 - Asterix and Obelix

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!
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman