No.3312 Fire Engine
Problem Statement
This country has $N$ cities, and all cities are connected to each other by roads. The time it takes to travel between cities $i$ and $j$ is $D_{ij}$.
In addition, the cafe chain "Math Cafe" has exactly $1$ store in every city of this country. At time $t = 0$, fires broke out simultaneously at all "Math Cafe" stores.
You are a firefighter. At time $t = 0$ you were in city $1$, and you immediately extinguished the fire at the "Math Cafe" store in city $1$.
Here, letting $t_i$ be the time at which the fire at the "Math Cafe" store in city $i$ was extinguished, the sadness $S$ is defined by the following formula. \[S = \sum_{1\le i\le N} t_i \]
Find the minimum achievable value of the sadness $S$. The time required to extinguish a fire is negligible.
Constraints
- $2 \leq N \leq 16$
- $1 \leq D_{ij} \leq 10000$ $(1 \leq i , j \leq N$ and $i \neq j)$
- $D_{ii} = 0$ $(1 \leq i \leq N)$
- $D_{ij} = D_{ji}$ $(1 \leq i , j \leq N)$
- For $1 \leq i , j \leq N$ and any $k$ $(1 \leq k \leq N)$, $D_{ij} \leq D_{ik} + D_{kj}$
- All inputs are integers
Input
$N$
$D_{11}$ $D_{12}$ $\dots$ $D_{1N}$
$D_{21}$ $D_{22}$ $\dots$ $D_{2N}$
$D_{31}$ $D_{32}$ $\dots$ $D_{3N}$
$\vdots$
$D_{N1}$ $D_{N2}$ $\dots$ $D_{NN}$
Output
Print a newline at the end.
Sample
Sample 1
Input
2 0 1942 1942 0
Output
1942
The minimum achievable value of the sadness $S$ is $1942$. In that case, $t_1 = 0, t_2 = 1942$ and $S = t_1 + t_2 = 1942$.
Sample 2
Input
4 0 3 6 11 3 0 4 9 6 4 0 5 11 9 5 0
Output
22
It is optimal to visit the cities in the order city $1$ → city $2$ → city $3$ → city $4$, in which case $t_1 = 0, t_2 = 3, t_3 = 7, t_4 = 12, S = 22$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Cafe1942