4128 - Steam Roller

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

Moderator: Board moderators

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

4128 - Steam Roller

Post by andmej » Wed May 14, 2008 6:40 pm

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

Post by dallmeyer » Tue Jun 24, 2014 10:34 am

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

Post by dallmeyer » Tue Jun 24, 2014 11:24 am

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.

Post Reply

Return to “ACM ICPC Archive Board”