Prester John (UVa Live Archive Europe - Southwestern - 2007/2008 Lisbon (Portugal))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3982

問題

辺に名前が付いた有向グラフが2つと目的地が2つ与えられる。2つの有向グラフの頂点0から同時に移動を開始して同じ名前の辺を通りながら目的地に行きたい。そのような最短経路の長さはいくらか。
頂点の数Lは1000
辺の数Pは10000

解法

同じ名前の辺を同時に通るようにしながら幅優先探索をすればよい。