1
$\begingroup$

Whilst preparing for the CCC(Canadian Computing Competition), I encountered CCC 2015 Seniors problem 4, linked here.

Anyway, the problem describes a set of vertices(points) numbered from $1$ to $N$, and a set of pathways $1$ to $M$, with pathway $p_i$ connecting two points $a_i,b_i$, taking time $t_i$. The goal of the problem is to find and print out the minimum time required to get from a specific point of $a$ to point $b$, along the pathways.

This looks like a Dijkstra's algorithm implementation... however there is a catch.

For every such pathway $p_i$ connecting two points $a_i,b_i$, not only is there a time $t_i$, there is also a hull value $k_i$. You travel by water along the pathways, and your ship has a hull $K$ to begin with. From point $a$ to point $b$, the sum of the hull values along your chosen pathway must not be greater than $K$, otherwise your ship will sink, i.e the pathway is no longer valid.

For this problem, what I first tried to do was to implement it similar to how a normal Dijikstra's algorithm would be implemented. enter image description here

This passed $9/15$ test cases on the grader, which I am quite proud of for a first attempt. Time wasn't an issue as it usually was, but I am getting Wrong Answer.

I then realised that I cannot just save the minimal hull value for each vertex, as each valid path has a different hull value sum. I have to implement a sort of queue/stack like structure and distinguish between each path.

However, the second I do that, I get codes that score even fewer points than my initial attempt. Time Limit becomes an issue, and I get even more Wrong Answer test cases on the practice CCC grader.

I spent two days already on this problem, and don't seem to be making any progress.

Any help will be appreciated.

$\endgroup$
2
$\begingroup$

Use the product construction to build a graph on $NK$ vertices and $MK$ edges, where each vertex records both which island you are at and how much hull you have left. Then, use Dijkstra's algorithm on that graph. The graph can be built on the fly and does not need to be constructed explicitly.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.