Translated from https://www.ioi-jp.org/joi/2020/2021-ho/2021-ho-t4-review.pdf
- You are given a simple undirected graph where the edges have colors.
- When giving instructions to the robot, you can only pick edges such that there's no other edge with the same color adjacent to the node where the robot is.
- Before giving the robot instructions, you want to paint the edges such that the robot can reach from node 1 to node N.
- Each edge has a cost associated with it; minimize the total cost of painting the edges.
- Since there are M colors, you can always paint an edge so that it has a different color than any other edge.
- Since you can paint all edges, you can always get from 1 to N unless they're disconnected in the graph.
- Consider an optimal solution. Think of the shortest path between 1 and N in such a graph.
- There's no point in painting edges that aren't adjacent to nodes in this path, so they weren't painted.
- Edges that connect nodes that are two steps or more away in this path weren't painted. If such an edge had been painted, we could have picked a different color for it and traversed it instead, getting a shorter path. [Tr: See diagram in page 10.]
- This means that as we go through a path, we can paint edges as we need. Furthermore, we don't need to consider any other edges other than the ones that are adjacent to our current node and the immediately prior one.
- N <= 1000, M <= 2000
- When choosing where to advance from a certain node, we have two kinds of options:
- X: Paint the edge we want to traverse and cross it.
- Y: Paint the other edges with the same color as the edge we want to traverse, and then cross it.
- We don't need to care about anything other than the previous node we visited. Other than that, we only need to care about these two options.
- We have reduced this problem to a shortest path in a graph. (Different from the one described in the problem statement.)
- We want the shortest path in the graph where the nodes are of the form (I am in node v, I painted edge e).
- Be careful that when choosing the edge to paint, it might be cheaper to do option Y.
- This new graph has N+2M nodes and (N+2M)N edges.
- Then, Dijkstra's algorithm runs in O(NM log(NM)).
- P = 1
- Option X is the best option as long as we can't advance for free otherwise. Since it's always useful to have painted the previous edge we traversed, it's best to prioritize option X rather than Y.
- In this case, when we pick option X, we don't even need to remember what we painted last. There's only a problem when want to take option Y and the new edge we want to traverse is the same color as the one we just traversed, which we might have painted in the last step.
- If we add a zero-cost edge between all nodes (I am in node v, I painted edge e) to (I am in node v, nothing is painted), now we need only care about the edges with the same color as the currently painted edge, if it exists.
- Furthermore, if there's three or more edges with the same color as a our edge e, option Y makes no sense. Then, given a node (v,e) there's at most only one possible option Y.
- Then, it is enough to find the shortest path in this graph, which has N + 2M nodes and 4M + 2M + 2M edges.
- (From before.) We only care about previously painted edges when we consider option Y.
- Let's enumerate all the transitions of the form u -> v (option X), v -> w (option Y) with respect to all possible vertices u.
- After taking a type-X transition from u to v but pretending it had cost 0, if we next take a type-Y transition from v to w forgetting that we painted the edge uv and do the cost calculation normally, we still get the correct result.
- We can add nodes of the form (I am in node v, Next I'll do a type-Y transition with color c), such that we can move to them with cost 0 from u. [Tr: See diagram in page 18.]
- There's up to N + 2M nodes and 2M + 4M edges.
- O(M log(M))
- We need a good way of handling the difficult-to-use node numbers to traverse this graph.
- It might be useful to use a
std::map<std::pair<int,int>,int>in C++. - For the edges associated with node v and color c, it makes no sense to choose option Y for any edge other than the two heaviest ones. This is because even if the heaviest edge has been painted, taking option X is still cheaper.
- We remove the edges that we added to the augmented graph in subtask 1.
- We add a cost-0 edge from (I am in node v, I painted edge e) to (I am in node v, No edges are painted).
- From (I am in node v, I painted edge e), we add the Y-transitions corresponding to the two heaviest edges with color e adjacent to v.
- This is fast enough as the number of added edges is linear.