配点: 点
から までの番号のついた 個の頂点と, 個の辺からなる,連結な重み付き無向グラフがあります.
を満たす任意の整数 について,頂点 と頂点 とを結ぶ,重み の辺が存在します.ただし です.
また,長さ の 正整数列 があり,このとき整数 に対して を次のように定めます:
さらに,任意の重み付きグラフに対して以下の操作を行うことができます:
操作
このグラフに対して,以上の操作を 回以上 回以下行うとき, の値は最小でいくつにすることができますか?
求めてください.
各テストケースの入力は,それぞれ以下の形式で与えられる:
答えを出力せよ.
1 9 1 1 2 4 2 3 3 1 3 5 6 1 6 6 6 2 6 3 4 1 5 6 9 2 8 3 9 4 8
39
頂点 を結ぶ辺に対して操作を 回行うことが最適です.
1 2 1 -1 3 1 2 1 2 1 2
-3