問題一覧 > 通常問題

No.1301 Strange Graph Shortest Path

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 130
作問者 : nok0nok0 / テスター : zkouzkou Kite_kumaKite_kuma
22 ProblemId : 5114 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-11-14 14:33:59

問題文

頂点に $1$ から $N$ まで、辺に $1$ から $M$ までの番号がついた $N$ 頂点 $M$ 辺の単純連結無向グラフが与えられます。

このグラフの辺 $i$ は頂点 $u_i$ と $v_i$ を双方向に結んでいて、長さは $c_i$ です。

ただし、一度辺 $i$ を通ると辺 $i$ の長さは $c_i$ から $d_i$ に変化します。ここで、 $c_i \le d_i$ であることが保証されます。

同一の辺は高々二回まで通ることができます。

頂点 $1$ から頂点 $N$ を通って頂点 $1$ に戻ってくる時の最短路の長さを求めてください。

制約

  • 入力は全て整数である。
  • 与えられるグラフは単純連結無向グラフである。
  • $2 \le N\le 10^5$
  • $N - 1 \le M\le \mathrm{min}\left(10^5, \frac{N (N - 1)} {2}\right)$
  • $1 \le u_i < v_i\le N$
  • $1 \le c_i \le d_i\le 10^{9}$

入力

$N\ M$
$u_1\ v_1\ c_1\ d_1$
$u_2\ v_2\ c_2\ d_2$
$\dots$
$u_M\ v_M\ c_M\ d_M$

出力

頂点 $1$ から頂点 $N$ を通って頂点 $1$ に戻ってくる時の最短路の長さを出力してください。

サンプル

サンプル1
入力
3 2
1 2 1 4
2 3 1 2
出力
8

頂点 $1$ から頂点 $N = 3$ を通って頂点 $1$ に戻ってくるには、 $1$ → $2$ → $3$ → $2$ → $1$ と頂点を移動するほかありません。最短路の長さは、$1 + 1 + 2 + 4 = 8$ です。

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

頂点を $1$ → $2$ → $3$ → $1$ と移動するのが最適で、最短路の長さは $1 + 1 + 1 = 3$ です。

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