Abandoning Roads
Contest: Codeforces Round 556 (Div. 1)
Difficulty rating: 3000
Tags: brute force, dp, graphs, greedy

Codefortia is a small island country located somewhere in the West Pacific. It consists of $$$n$$$ settlements connected by $$$m$$$ bidirectional gravel roads. Curiously enough, the beliefs of the inhabitants require the time needed to pass each road to be equal either to $$$a$$$ or $$$b$$$ seconds. It's guaranteed that one can go between any pair of settlements by following a sequence of roads.

Codefortia was recently struck by the financial crisis. Therefore, the king decided to abandon some of the roads so that:

- it will be possible to travel between each pair of cities using the remaining roads only,
- the sum of times required to pass each remaining road will be minimum possible (in other words, remaining roads must form minimum spanning tree, using the time to pass the road as its weight),
- among all the plans minimizing the sum of times above, the time required to travel between the king's residence (in settlement $$$1$$$) and the parliament house (in settlement $$$p$$$) using the remaining roads only will be minimum possible.

The king, however, forgot where the parliament house was. For each settlement $$$p = 1, 2, \dots, n$$$, can you tell what is the minimum time required to travel between the king's residence and the parliament house (located in settlement $$$p$$$) after some roads are abandoned?

Input format:
The first line of the input contains four integers $$$n$$$, $$$m$$$, $$$a$$$ and $$$b$$$ ($$$2 \leq n \leq 70$$$, $$$n - 1 \leq m \leq 200$$$, $$$1 \leq a < b \leq 10^7$$$) — the number of settlements and gravel roads in Codefortia, and two possible travel times. Each of the following lines contains three integers $$$u, v, c$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$c \in \{a, b\}$$$) denoting a single gravel road between the settlements $$$u$$$ and $$$v$$$, which requires $$$c$$$ minutes to travel.

You can assume that the road network is connected and has no loops or multiedges.

Output format:
Output a single line containing $$$n$$$ integers. The $$$p$$$-th of them should denote the minimum possible time required to travel from $$$1$$$ to $$$p$$$ after the selected roads are abandoned. Note that for each $$$p$$$ you can abandon a different set of roads.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
The minimum possible sum of times required to pass each road in the first example is $$$85$$$ — exactly one of the roads with passing time $$$25$$$ must be abandoned. Note that after one of these roads is abandoned, it's now impossible to travel between settlements $$$1$$$ and $$$3$$$ in time $$$50$$$.

Example input:
5 5 20 25
1 2 25
2 3 25
3 4 20
4 5 20
5 1 20

Example output:
0 25 60 40 20

Example input:
6 7 13 22
1 2 13
2 3 13
1 4 22
3 4 13
4 5 13
5 6 13
6 1 13

Example output:
0 13 26 39 26 13

Editorial:
Let's partition the edges of the graph into two classes: light (weight $$$a$$$) and heavy (weight $$$b$$$). Let's now fix a single settlement $$$p$$$ as the location of the parliament house, and consider how the path between settlements $$$1$$$ and $$$p$$$ could look like.
Lemma 1. If there is a path between two settlements $$$u$$$, $$$v$$$ consisting of light edges only, then they will be connected using the light edges only in any minimum spanning tree.
Proof. Consider the Kruskal minimum spanning tree algorithm (which can produce any minimum spanning tree depending on the order we consider the edges with equal weight). After we process all light edges, settlements $$$u$$$ and $$$v$$$ will be connected.
Lemma 2. Consider the connected components in the graph with heavy edges removed. In the original graph, a path can be a part of the minimum spanning tree if and only if there is we don't leave and then reenter any of the components.
Proof. If we leave and then reenter any connected component, there are two vertices $$$u$$$, $$$v$$$ in a single connected component (that is, connected by a light path in the original graph) that has at least one heavy edge on the path in between. Lemma 1 asserts that it's impossible. However, if no such situation happens, it's straightforward to extend the selected path to a minimum spanning tree — first add all possible light edges, then all possible heavy edges so that the graph becomes a spanning tree.
This leads us to an (inefficient) $$$O(2^n m \log(2^n m))$$$ solution: find the connected components in the graph with light edges only. We want now to find the shortest path between $$$1$$$ and all other vertices that doesn't revisit any component multiple times. In order to do so, create a graph where each state is of the following format $$$(\text{mask of components visited so far}, \text{current vertex})$$$. This information allows us to check if we don't reenter any previously visited component. After we do that, we run Dijkstra's shortest path algorithm from vertex $$$1$$$. The shortest path between vertices $$$1$$$ and $$$p$$$ can be found in the state first visiting vertex $$$p$$$.
The beautiful thing now is that the algorithm can be sped up by the following greedy observation:
Lemma 3. Consider any component of size $$$3$$$ or less. It's not optimal to leave and then reenter this component even if we don't explicitly forbid this.
Proof. We need to use at least two heavy edges to leave and then reenter the component, and this costs us $$$2b$$$ or more. However, as the component has at most three vertices, the path between any pair of vertices costs at most $$$2a$$$. As $$$a < b$$$, it's always more optimal to take the path inside the component.
Therefore, we can simply ignore all components of size $$$3$$$ or less. As we now need to remember the components having at least $$$4$$$ vertices, the number of states drops down to $$$O(2^{n/4} m)$$$. This immediately allows us to finish the solution in a number of ways:
• Implement the vanilla Dijkstra algorithm on the state graph — time complexity $$$O(2^{n/4} m \log(2^{n/4} m))$$$.
• Notice that the edges of the graph have only two weights ($$$a$$$ and $$$b$$$) and therefore the priority queue can be implemented using two queues — time complexity drops to $$$O(2^{n/4} m)$$$.