CODE FESTIVAL 2014 Easy C – 身体バランス を解いた記録
問題の概要
\(n\)頂点\(m\)辺の重み付き無向グラフが与えられる．頂点\(s\)から頂点\(t\)へ至る経路を考える．
ある頂点\(u\)を選び，頂点\(s\)から頂点\(u\)までの経路上の辺の重みの和と頂点\(u\)から頂点\(t\)までの経路上の辺の重みの和が等しくなるようにしたい．
頂点\(s\)から頂点\(u\)までの経路上の辺の重みの和と頂点\(u\)から頂点\(t\)までの経路上の辺の重みの和が等しくなるような頂点\(u\)が存在するならば，そのような頂点の番号を出力せよ．
条件を満たす頂点が複数存在する場合は，条件を満たすどの頂点の番号を出力しても正解となる．
条件を満たす頂点が存在しない場合は，\(-1\)を出力せよ．
注意
- 頂点\(s\)から頂点\(u\)までの経路，頂点\(u\)から頂点\(t\)までの経路については，経路上の辺の重みの和が最小でなければならない．
- 頂点\(s\)から頂点\(u\)を経由し，頂点\(t\)に到達するまでの経路については，経路上の辺の重みの和が最小でなくてもよい．
- 頂点\(s\)から頂点\(t\)までの経路の存在は保証される．ただし，グラフ全体が連結であるとは限らない．
制約
- \(3 \leq n \leq 1000\)
- \(1 \leq m \leq \min(n(n-1)/2, 10^{4})\)
- \(1 \leq s, t \leq n\)
- \(s \neq t\)
- 入力はすべて整数
解法
頂点\(s\)から各頂点までの最短経路長は，ダイクストラ法により求められます．頂点\(t\)から各頂点までの最短経路長も，ダイクストラ法により求められます．
よって，次の手順でこの問題を解けます．
- 頂点\(s\)から各頂点までの最短経路長及び頂点\(t\)から各頂点までの最短経路長を，ダイクストラ法で求める．
- 各頂点について，頂点\(s\)からの最短経路長と頂点\(t\)からの最短経路長を比較する．
頂点\(s\)からの最短経路長と頂点\(t\)からの最短経路長が一致する場合は，その頂点の番号が答えとなる． - どの頂点についても頂点\(s\)からの最短経路長と頂点\(t\)からの最短経路長が一致しない場合，条件を満たす頂点は存在しない．
グラフ全体としては非連結である場合があるため，ある頂点について頂点\(s\)からの最短経路長と頂点\(t\)からの最短経路長を比較するときには，
その頂点が頂点\(s\)及び頂点\(t\)から到達可能であることを検査する必要があります．