Məsələlər
Fly or not fly
Fly or not fly
Welcome to Mars! Your first mission is to send letters to \textbf{K} cities \textbf{A_1}, \textbf{A_2}, …, \textbf{A_K} in order. Mars consists of \textbf{N} cities connected by roads, different roads may have different lengths, in city \textbf{i} there are \textbf{P_i} UFOs which you can take to increase your speed, let’s assume that the road’s length is \textbf{x}, so if you walk through this road, you’ll spend \textbf{5x} minutes, but if you fly (by UFO of course), you’ll only spend \textbf{x} minutes. However, you must have this mission done in minimal time, and each UFO can only be used once, it disappears when you leave it, you can’t send letters when you are in the UFO, so you must leave it in order to send a letter.
\InputFile
There are several test cases, end with \textbf{EOF}. For each test case, the first line contains two integers \textbf{N} ≤ \textbf{100}, and\textbf{K} ≤ \textbf{N}, the second line is \textbf{N} integers, \textbf{P_1}, \textbf{P_2}, …, \textbf{P_N}.(\textbf{P_i} ≤ \textbf{10}), Next \textbf{N} lines is an \textbf{N}×\textbf{N} matrix \textbf{G}_\{1..N,1..N\} for the lengths between every two cities(\textbf{G_\{i,j\}} ≤ \textbf{100}), it is guaranteed that \textbf{G_\{i,j\}=G_\{j,i\}} and \textbf{G_\{i,i\}=0}, if \textbf{G_\{i,j\}=-1}, it means that there is no road between city \textbf{i} and \textbf{j}. The last line of each case is \textbf{K} integers \textbf{A_1}, \textbf{A_2}, …, \textbf{A_K}. You are in city \textbf{A_1} at first.
\OutputFile
For each the case, output the minimal time.
Giriş verilənləri #1
3 3 0 0 1 0 -1 1 -1 0 1 1 1 0 1 3 2 3 3 2 0 0 0 -1 1 -1 0 100 1 100 0 1 3 2
Çıxış verilənləri #1
6 107
Şərh: Case 1: First walk 1->3 (spend 5 minutes), and take UFO in 3, fly 3->2 (spend 1 minute), total 6 minutes. Case 2: First take UFO in 1, fly 1->3 (spend 1 minute), walk back 3->1 (spend 5 minutes) and take UFO in 1 again, fly 1->2 (spend 101 minutes), total