## 4128 - Steam Roller

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### 4128 - Steam Roller

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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

dallmeyer
New poster
Posts: 2
Joined: Tue Jun 24, 2014 10:33 am

### Re: 4128 - Steam Roller

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

dallmeyer
New poster
Posts: 2
Joined: Tue Jun 24, 2014 10:33 am

### Re: 4128 - Steam Roller

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.