問題一覧 > 通常問題

No.3312 Fire Engine

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 49
作問者 : Cafe1942 / テスター : 👑 loop0919 sclara
お気に入りにしたユーザー ProblemId : 12786 / 自分の提出
問題文最終更新日: 2025-10-24 08:12:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 486 オムニバス (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。