No.1301 Strange Graph Shortest Path

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 132
作問者 :

nok0 / テスター :

zkou

Kite_kuma

23 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} \leq d_{i}$ であることが保証されます。

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

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

 $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$ に戻ってくる時の最短路の長さを出力してください。

3 2
1 2 1 4
2 3 1 2

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

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

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