OJ Board

Posted: **Mon May 01, 2006 9:12 am**

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!

Posted: **Mon May 01, 2006 12:00 pm**

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

Posted: **Sun May 07, 2006 2:20 am**

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.

Posted: **Sat Apr 19, 2008 2:31 am**

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] )

Posted: **Mon May 05, 2008 11:08 am**

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?

Posted: **Mon May 05, 2008 4:10 pm**

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?

Posted: **Tue May 06, 2008 11:11 am**

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

Posted: **Tue Sep 11, 2012 5:32 pm**

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

Posted: **Sun Nov 04, 2012 2:15 pm**

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

Posted: **Mon Nov 04, 2013 11:45 am**

brianfry713 wrote: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.

Posted: **Tue Jul 08, 2014 2:11 pm**

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

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

Posted: **Tue Jul 08, 2014 9:45 pm**

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

Posted: **Sat Jul 12, 2014 4:49 pm**

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..

Posted: **Mon Jul 14, 2014 6:38 pm**

Try using Floyd-Warshall's algorithm twice.

Posted: **Tue Jul 15, 2014 2:26 pm**

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!

OJ Board

10246 - Asterix and Obelix

Re:

Re: 10246 - Asterix and Obelix

Re: 10246 - Asterix and Obelix

Re: 10246 - Asterix and Obelix

Re: 10246 - Asterix and Obelix

Re: 10246 - Asterix and Obelix

Re: 10246 - Asterix and Obelix

Re: 10246 - Asterix and Obelix

Re: 10246 - Asterix and Obelix

Re: 10246 - Asterix and Obelix

Re: 10246 - Asterix and Obelix

Re: 10246 - Asterix and Obelix