Problem B
K-Walks
It is the final team contest. After some persuasion from his fellow problem setters, Lord Pooty decided to make an easy problem. Today, he was thinking about shortest path problems. It is a classic problem with many variants. Today, he decided to ask you on one interesting variant (in set-theoretic notation!!).
Consider finite sets $S_1$ and $S_2 \subseteq \{ s \subseteq S_1: |s| = 2\} $, $K \in \mathbb {N}$, $f \in {\mathbb {N}}^{S_2}$.
Define:
\begin{align*} T\colon S_1 \times S_1 \to & \mathcal{P}(\mathbb {Z}_{\geq 0}) \\ (i,j) \mapsto & \{ x \in \mathbb {Z}_{\geq 0}\colon (\exists B \in S_2^{< \omega }) [ (\exists A \in S_1^{|B| + 1})[(B_ k = \{ A_{k}, A_{k+1}\} \forall k \in \mathbb {N}, k \leq |B|) \\ & \land (A_1 = i) \land (A_{|B|+1} = j)] \land (\sum _{b \in B}f(b) = x)] \land (K|x)\} \\ H\colon \mathcal{P} (\mathbb {Z}_{\geq 0})\to & \mathbb {Z}_{\geq -1} \\ X \mapsto & \left\{ \begin{array}{ll} \min (X) & \mbox{if } X \neq \emptyset \\ -1 & \mbox{if }X = \emptyset \end{array} \right. \end{align*}$\forall i,j\in S_1$,
output $H\circ
T(i,j)$.
In most circumstances, you are expected to understand the abstract nonsense above which is more than sufficient to answer the question. However, Lord Pooty is benevolent. As such, he has provided to you the readable but mostly accurate translation below:
You are given a undirected simple weighted graph with integer edge weights that is not necessarily connected. Print the length of the K-walk (shortest finite walk 1 where the total edge weight is a multiple of $K$) from one vertex to another if it exists, or $-1$ otherwise. Do this for all pairs of vertices.
Input
The first line contains integers $V, E, K$. ($1 \leq V \leq 100$), ($0 \leq E \leq \min (200, \frac{V*(V-1)}{2}$), ($1 \leq K \leq 2^{63} -1$).
This is followed by $E$ lines: $u, v, w$ ($1 \leq u,v \leq V$), ($1 \leq w \leq 200$). This denotes a undirected edge from $u$ to $v$ of weight $w$. Furthermore, the sum of all edge weights is at most $200$.
Output
Output $V$ lines of $V$ integers, where the $j$ number of the $i$ line refers to the length of the $K$-walk from $i$ to $j$. Since the numbers can be huge, output up to the last $7$ digits for each integer where there exist K-walk or $-1$ otherwise.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 1 1 2 2 2 3 1 |
0 2 3 2 0 1 3 1 0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 1 9223372036854775807 1 2 2 |
0 9551614 9551614 0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 2 10 1 2 15 2 3 15 |
0 -1 30 -1 0 -1 30 -1 0 |
Footnotes
- Intuitively, you can think of a walk as a path with repeated vertices or edges. However strictly speaking this is wrong as a path is a subset of a walk (not the other way around!) which does not have repeated vertices or edges.
