ABC132 E - Hopscotch Addict - あっとのTECH LOG

問題原文

問題要旨

$N$ 頂点 $M$ 辺の有向グラフが与えられる。このグラフ上での移動は、「ケンケンパ」によって行う。具体的には、隣接する頂点への移動は常に３回連続で行う。この条件の元、頂点 $S$ から頂点 $T$ にたどり着くまでの最小のケンケンパの回数を求めよ。

$1 \leq N \leq 10^{5}$
グラフは自己ループや多重辺を含まず、辺数は最大 $10^{5}$ 本

解法

単純なグラフに、「ケン・ケン・パのどのタイミングで訪れたか」を管理する仕組みを取り入れたい。
これは頂点数を３倍に増やし、それぞれ「１回目のケンで訪れる場合」「２回目のケンで訪れる場合」「パで訪れる場合」とすればいい。
あとはDFSでもBFSでもダイクストラでも使って、「パで $S$ を訪れた状態」から「パで $T$ を訪れる」まで何回移動するかを求めればよい。

実装

N, M = map(int, input().split())
G = [[] for i in range(3 * N)]
for i in range(M):
    u, v = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v + N, 1]) 
    G[u + N].append([v + 2 * N, 1]) 
    G[u + 2 * N].append([v, 1]) 

S, T = map(int, input().split())
S, T = S - 1, T - 1

distances = dijkstra(G, S)
print(distances[T] // 3 if distances[T] != float('inf') else -1)

感想

こういうのを頂点倍化っていうんだろうか。
頂点になんらかの追加情報を持たせたい時、頑張って各頂点に持たせるのではなく、そのような状態に対応する頂点を追加することで問題を簡単にする考え方はいろんなところで使えそうですね。