問題一覧 > ネタ問題

No.3078 Very Simple Traveling Salesman Problem

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 151
作問者 : NatsubiSoganNatsubiSogan / テスター : aspiaspi
1 ProblemId : 6063 / 出題時の順位表
問題文最終更新日: 2021-04-06 11:08:27

問題文

頂点に $1$ から $N$ までの、辺に $1$ から $M$ までの番号のついた、$N$ 頂点 $M$ 辺の単純連結無向グラフが与えられます。 辺 $i$ は頂点 $u_i$ と $v_i$ を重み $w_i$ で双方向に結んでいます。

ある頂点から出発して、すべての頂点をちょうど $1$ 度ずつ通り、出発点に戻るような巡回路であって、その重みが最小であるようなものの重みを求めてください。

この問題の制約下で、そのような巡回路が少なくとも $1$ つ存在することが示せます。

入力

$N\ M$
$u_1\ v_1\ w_1$
$u_2\ v_2\ w_2$
$\vdots$
$u_M\ v_M\ w_M$

  • 入力はすべて整数
  • 与えられるグラフは単純かつ連結
  • $2 \leq N \leq 500$
  • $M=\displaystyle \frac{N(N-1)}{2}$
  • $1 \leq u_i,v_i \leq N$
  • $w_i=1$

出力

問題文の条件を満たす巡回路の重みの最小値を $1$ 行に出力してください。

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

サンプル

サンプル1
入力
2 1
1 2 1
出力
2

往復して帰ってくるしかありません。

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