4128 - Steam Roller

[andmej]

Hello, I'm trying to solve this problem: K - Steam Roller from the 2008 Alberta ICPC Finals. I'm getting wrong answer.

I'm using Dijkstra's algorithm to solve it. Can you give me some tricky input?

Here's some input I've tried, is it right?

Input:

Code: Select all

4 4 1 1 4 4 
 10  10  10 
9  0  0  10 
  0  0  0 
9  0  0  10 
  9  0  0 
0  9  0  10 
  0  9  9 

2 2 1 1 2 2
 0
1 1
 0 

2 4 2 1 2 3
 0 0 1
0 0 1 1
 1 9 1

1 2 1 1 1 2
100

3 3 2 2 2 3
 1 1
1 1 1
 1 1
1 1 1
 1 1

1 2 1 1 1 2
0

4 4 1 1 4 4
2 0 8
10000 3 7 9
   0 0 0
10000 4 6 10
   0 5 0
10000 0 0 11
10000 10000 10000

0 0 0 0 0 0

My program outputs:

Code: Select all

Case 1: 100
Case 2: Impossible
Case 3: 15
Case 4: 200
Case 5: 2
Case 6: Impossible
Case 7: 120

Thanks.

[dallmeyer]

I am also getting WA, but my solution produces the same output for your input.

[dallmeyer]

Alright well I just figured mine out, I was setting the shortest path through the starting point to 0 from all 4 directions and when stopped, when you really only need to set it for stopped.
There is a test case where the shortest path goes back through the starting point, which mine would never try since it thinks the shortest path is 0.
If you want to run any test cases against my data just let me know.