問題一覧 > 通常問題

No.1320 Two Type Min Cost Cycle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 56
作問者 : 👑 ningenMeningenMe / テスター : 👑 maspymaspy
6 ProblemId : 5567 / 出題時の順位表
問題文最終更新日: 2020-12-16 02:10:13

問題文

整数 $T$ と $N$ 頂点 $M$ 辺からなる重み付きグラフが与えられます。
このグラフには同一の $2$ 頂点間を結ぶ辺は $1$ つまでしか存在しません。またこのグラフには両端の頂点が同じであるような辺は存在しません。


$T$ は $0$ あるいは $1$ のどちらかの値です。

  • $T=0$ のとき

    与えられるグラフは無向グラフです。 $i$ 番目の辺は頂点 $u_i$ と $v_i$ を重み $w_i$ で双方向に接続しています。

  • $T=1$ のとき

    与えられるグラフは有向グラフです。 $i$ 番目の辺は頂点 $u_i$ から $v_i$ に重み $w_i$ で接続しています。


与えられるグラフに含まれる最小の閉路の大きさを求めてください。閉路の大きさとは、含まれる辺の重みの和です。 閉路が存在しない場合は-1を出力してください。

注意

  • 閉路の定義に関しては、閉路グラフの説明を参照してください。
  • TLの制約上、pythonユーザの方はpypyで提出することを推奨します。

入力

$T$
$N\ M$
$u_1\ v_1\ w_1$
$\vdots$
$u_M\ v_M\ w_M$
  • 与えられる入力は全て整数
  • $0 \le T \le 1$
  • $1 \le N \le 2000$
  • $0 \le M \le \min( 2000, N(N-1)/2) $
  • $1 \le u_i \le N$
  • $1 \le v_i \le N$
  • $1 \le w_i \le 10^9$
  • $u_i \neq v_i $
  • $(u_i,v_i) \neq (u_j,v_j) \ (i \neq j) $
  • $(u_i,v_i) \neq (v_j,u_j) \ (i \neq j) $

出力

与えられるグラフに含まれる最小の閉路の大きさを求めてください。閉路が存在しない場合は-1を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
0
4 5
1 2 1
2 3 2
2 4 3
1 3 4
4 1 5
出力
7

頂点を$(1,2,3,1)$の順に巡る経路が最小の閉路の一つです。

サンプル2
入力
1
4 5
1 2 1
2 3 2
2 4 3
1 3 4
4 1 5
出力
9

頂点を$(1,2,4,1)$の順に巡る経路が最小の閉路の一つです。

サンプル3
入力
0
3 1
1 2 1
出力
-1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。