UVa 12950 - Even Obsession

Source

Latin America - Brazil Sub Regional(20150913)
UVa 12950

問題概要

$C$ 個の街(番号は $1$ から $C$)と,$V$ 個の双方向に移動できる道路がある.
道路は $2$ つの街を繋いでいて,$i$ 番目の道路を通るには $G_i$ だけ料金がかかる.
街 $1$ から街 $C$ に移動したいが偶数回の料金を支払うような経路の中で,最も安く移動する方法で移動する.
可能ならばそのコストを,不可能ならばそれを指摘する問題.

解法

今まで何本の枝を通ったかの偶奇でノードを拡大し,その上でダイクストラすれば良い.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年09月21日05時11分00秒
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)

ログイン: