UVa 12950 - Even Obsession

Source

Latin America - Brazil Sub Regional（20150913）
UVa 12950

問題概要

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

テストケースの数に対する制約はない
$2 \leq C \leq 10000\ (10^4)$
$0 \leq V \leq 50000\ (5 \times 10^4)$
$1 \leq G_i \leq 10000\ (10^4)$

解法

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

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)