{"raw_statement":[{"iden":"statement","content":"Мирлин Теренс тщетно пытался спасти Рика и Валлону от агентов Трантора. Переодевшись патрульным, он разыскивал их по всему Верхнему городу, однако никак не мог напасть на их след. Встреча произошла уже недалеко и космопорта, но тут завязалась перестрелка между Теренсом и агентом, а Рик и Валлона, не узнав Мирлина, сбежали, и уже летели на космическом корабле до Сарка. Теренс понимал, что не может лететь вслед за ними на корабле — его тут же узнают. Однако у многих зажиточных граждан Верхнего города были космические яхты, путешествие на которой вызвало бы намного меньше подозрений. Конечно, Теренс к этим гражданам не относился и ключей от яхты не имел, но форма патрульного, оружие и полумрак ночных улиц помогли их раздобыть.\n\nТеренс все еще должен был оставаться незамеченным, и потому ему стоило избегать встречи с патрульными. Квартал рядом с портом состоит из $n$ перекрестков, соединенных $m$ дорожками с односторонним движением, для каждой дорожки известно, за какое время ее можно преодолеть. Посреди ночи по кварталу ходили всего двое патрульных, которые сейчас находятся на перекрестках $s_1$ и $s_2$. По рации, отобранной у патрульного, Теренс узнал, что они должны обойти $k$ перекрестков $p_1, p_2,... p_k$ в заданном порядке (один перекресток может встречаться в этом списке несколько раз). Обходить они будут по одному, то есть на каждом из заданных перекрестков может побывать один из патрульных. Они действуют следующим образом: сначала какой-либо из патрульных доходит до перекрестка $p_1$ и сообщает об этом напарнику. После этого какой-либо патрульный начинает свое движение до перекрестка $p_2$. Так происходит, пока патрульные не осмотрят перекресток $p_k$, после чего их смена заканчивается. Если в какой-то момент патрульным необходимо проверить перекресток $i$, и какой-то из патрульных как раз находится на этом перекрестке, они переходят к проверке следующего перекрестка. При необходимости патрульные могут находиться на одном перекрестке. Патрульные хотят как можно быстрее закончить свою работу, а потому выбирают пути и разделяют между собой перекрестки таким образом, чтобы обход занял минимальное время.\n\nМирлин Теренс решил, что проще всего проникнуть в порт во время смены патрульных. Поэтому он спрашивает вас: сколько времени патрульные будут совершать обход, если они выбирают свои пути оптимально?\n\nВ первой строке записаны три числа: $n, m$ и $k$ $(1 <= n <= 300, 0 <= m <= n dot.op (n -1), 1 <= k <= 1000)$ — количество перекрестков, дорожек и количество перекрестков, которые должны осмотреть патрульные, соответственно.\n\nВ следующих $m$ строках через пробел записаны по три числа: $v_i, u_i$ и $t_i$ $(1 <= v_i, u_i <= n, 1 <= t_i <= 10^6)$, означающие, что от перекрестка с номером $v_i$ идет дорожка к перекрестку с номером $u_i$, по которой можно пройти за время $t_i$.\n\nВ следующей строке через пробел записаны номера перекрестков $p_1, p_2, \\\\dots p_k$.\n\nВ последней строке через пробел записаны два числа — $s_1$ и $s_2$.\n\nВыведите одно число — время обхода патрульных, либо число $-1$, если патрульные не смогут обойти перекрестки в заданном порядке.\n\nВ первом примере между перекрестками нет ни одной дорожки, но патрульные находятся на $5$-м и $4$-м перекрестках. Так как патрульным требуется проверить $5, 5, 4, 4$ и $5$ перекрестки, им остается лишь стоять на месте каждый раз. Таким образом, на перемещение время тратиться не будет.\n\nВо втором примере оптимален следующий алгоритм. Первый патрульный перемещается с $1$-го перекрестка на $5$-й за $3$ единицы времени, а затем возвращается на $1$ перекресток за $10$ единиц времени. После этого второй патрульный, находясь на $2$-м перекрестке проверяет его и переходит на $3$-й перекресток за $2$ единицы времени. Таким образом, получаем суммарное время: $3 + 10 + 2 = 15$.\n\n"},{"iden":"входные данные","content":"В первой строке записаны три числа: $n, m$ и $k$ $(1 <= n <= 300, 0 <= m <= n dot.op (n -1), 1 <= k <= 1000)$ — количество перекрестков, дорожек и количество перекрестков, которые должны осмотреть патрульные, соответственно.В следующих $m$ строках через пробел записаны по три числа: $v_i, u_i$ и $t_i$ $(1 <= v_i, u_i <= n, 1 <= t_i <= 10^6)$, означающие, что от перекрестка с номером $v_i$ идет дорожка к перекрестку с номером $u_i$, по которой можно пройти за время $t_i$.В следующей строке через пробел записаны номера перекрестков $p_1, p_2, \\\\dots p_k$.В последней строке через пробел записаны два числа — $s_1$ и $s_2$."},{"iden":"выходные данные","content":"Выведите одно число — время обхода патрульных, либо число $-1$, если патрульные не смогут обойти перекрестки в заданном порядке."},{"iden":"примеры","content":"Входные данные5 0 5\n5 5 4 4 5\n5 4\nВыходные данные0\nВходные данные5 4 4\n1 5 3\n5 1 10\n1 2 1\n2 3 2\n5 1 2 3\n1 2\nВыходные данные15\n"},{"iden":"примечание","content":"В первом примере между перекрестками нет ни одной дорожки, но патрульные находятся на $5$-м и $4$-м перекрестках. Так как патрульным требуется проверить $5, 5, 4, 4$ и $5$ перекрестки, им остается лишь стоять на месте каждый раз. Таким образом, на перемещение время тратиться не будет.Во втором примере оптимален следующий алгоритм. Первый патрульный перемещается с $1$-го перекрестка на $5$-й за $3$ единицы времени, а затем возвращается на $1$ перекресток за $10$ единиц времени. После этого второй патрульный, находясь на $2$-м перекрестке проверяет его и переходит на $3$-й перекресток за $2$ единицы времени. Таким образом, получаем суммарное время: $3 + 10 + 2 = 15$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ denote the number of intersections, directed roads, and checkpoints respectively.  \nLet $ G = (V, E) $ be a directed graph with $ V = \\{1, 2, \\dots, n\\} $ and $ E \\subseteq V \\times V $, where each edge $ (v_i, u_i) \\in E $ has weight $ t_i \\in \\mathbb{Z}^+ $.  \nLet $ P = (p_1, p_2, \\dots, p_k) \\in V^k $ be the sequence of checkpoints to be visited in order.  \nLet $ s_1, s_2 \\in V $ be the initial positions of the two patrols.  \n\nLet $ d(u, v) \\in \\mathbb{R}_{\\geq 0} \\cup \\{\\infty\\} $ denote the shortest path distance from $ u $ to $ v $ in $ G $, computed via all-pairs shortest paths (e.g., Floyd-Warshall). If no path exists, $ d(u, v) = \\infty $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 300 $  \n2. $ 0 \\leq m \\leq n(n-1) $  \n3. $ 1 \\leq k \\leq 1000 $  \n4. $ 1 \\leq t_i \\leq 10^6 $  \n5. For all $ i \\in \\{1, \\dots, k\\} $, $ p_i \\in V $  \n6. $ s_1, s_2 \\in V $  \n\n**Objective**  \nCompute the minimum total time required for two patrols to visit checkpoints $ p_1, p_2, \\dots, p_k $ in order, such that:  \n- At step $ j \\in \\{1, \\dots, k\\} $, **exactly one** patrol moves from its current position to $ p_j $.  \n- If a patrol is already at $ p_j $, no movement is needed (time cost = 0).  \n- Patrols may occupy the same intersection.  \n- The goal is to minimize the sum of movement times over all steps.  \n\nDefine $ \\text{dp}[j][a][b] $ as the minimum time to have completed visiting the first $ j $ checkpoints, with patrol 1 at position $ a \\in V $ and patrol 2 at position $ b \\in V $.  \n\nInitialize:  \n$ \\text{dp}[0][s_1][s_2] = 0 $, and all other $ \\text{dp}[0][a][b] = \\infty $.  \n\nTransition:  \nFor each $ j \\in \\{1, \\dots, k\\} $, and for all $ a, b \\in V $:  \n$$\n\\text{dp}[j][p_j][b] = \\min_{a' \\in V} \\left( \\text{dp}[j-1][a'][b] + d(a', p_j) \\right) \\\\\n\\text{dp}[j][a][p_j] = \\min_{b' \\in V} \\left( \\text{dp}[j-1][a][b'] + d(b', p_j) \\right)\n$$  \n(If $ p_j = a $, then $ d(a, p_j) = 0 $; same for $ b $.)  \n\nFinal answer:  \n$$\n\\min_{a, b \\in V} \\text{dp}[k][a][b]\n$$  \nIf the minimum is $ \\infty $, output $ -1 $.","simple_statement":"Two police officers start at positions s1 and s2 on a directed graph with n nodes and m weighted edges. They must visit k checkpoints in order: p1, p2, ..., pk. At each step, either officer can move to the next checkpoint. They can be on the same node. Find the minimum total time needed to complete all checks, or -1 if impossible.","has_page_source":false}