Unidirectional TSP Take Two! (116)

I have previously blogged about my abysmal failures at solving the beast. Today, I did what I could could not in April.

First, I did a solution which didn't work in Java. Then I retried it. Still "wrong answer." Then I retried again. I fixed all the problems, but I got a "Time-limit Exceeded" error. I was so frustrated I gave up, which I typically don't do.

Last night, about 10 o'clock, the other members of my programming team Ian and Angus suggested I try to to practice my dynamic programming skills.

I knew what was inefficient about my Java implementation, but I didn't want to fix it. Instead, I wrote a new implementation in C++. I struggled for a while with compiler errors and language oddities, but got it in the end. Testing took about half an hour, but I still couldn't get it. Finally, at 12:45 am this morning, I submitted with a "Presentation error", which means I got the correct answer, but I didn't output my data in the correct format.

This morning, I finally corrected the errors. What was the problem? This question is very particular about spaces between paths, costs, etc. You need a newline after your last test case and spaces in between each element of the shortest path, but not after the last element of the path.

Hope that helps anyone else out there doing Unidirectional TSP for the UVa judge!