Latin America - Brazil Sub Regional(20150913)
UVa 12950
$C$ 個の街(番号は $1$ から $C$)と,$V$ 個の双方向に移動できる道路がある.
道路は $2$ つの街を繋いでいて,$i$ 番目の道路を通るには $G_i$ だけ料金がかかる.
街 $1$ から街 $C$ に移動したいが偶数回の料金を支払うような経路の中で,最も安く移動する方法で移動する.
可能ならばそのコストを,不可能ならばそれを指摘する問題.
今まで何本の枝を通ったかの偶奇でノードを拡大し,その上でダイクストラすれば良い.
この部分を表示するには表示権限を持つユーザーでログインする必要があります.
Current time: 2024年04月18日11時47分36秒
Last modified: 2015年09月14日20時29分00秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20150913_1
トップページに戻る
Logged in as: unknown user (not login)