ICPC/domestic/2004F

出展 †

• ICPC国内予選2004 問題文(AOJ)

解法 †

• グラフ上の経路探索問題として解くことができる
  • 通りの名前に対応するノードを作り，
    • 交差点の名前A-Bが存在すれば，A→Bへ長さ1の枝を張る
    • 通りAとBが同水準ならA→BおよびB→Aに長さ2の枝を張る
  • 通りの名前C-Dが与えられたとき，C→Dに奇数長さの経路が存在すれば名前は有効

回答 †

• 2004F_pes.cpp - ワーシャルフロイド(pes)