いろはちゃんコンテスト Day1 I - リスのお仕事

久しぶりに拡張ダイクストラの問題
day2 にも拡張ダイクストラが出ていたりする。
ダイクストラといっても、距離は一切出てこなくて、休憩回数の最小値を求める問題。
heap で (累計の休憩回数、前の隙間、今いる頂点）を保管して、今いる頂点から次の頂点に行くときに、その辺の隙間 != 前の隙間なら休憩回数を +1 して heap に入れ、= ならそのまま heap に入れる。
個人的には、同じ辺を二回以上通らないための工夫に悩んだが、考えると、heap でループしているので、ある頂点 i に初めて来た時の休憩回数が 1 から i に行くときの最小の休憩回数といえるので、heap で一回取り出された頂点にはもう行かなくていいと分かったので解決した。

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop

N,M,K = map(int,readline().split())
ABC = [list(map(int,readline().split())) for _ in range(M)]

graph = [[] for _ in range(N)]
for a,b,c in ABC:
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))

ans = -1
used = [False]*N
used[0] = True
q = [(0,0,0)]
while q:
  t,pre,now = heappop(q)
  if now == N-1:
    ans = t
    break
    # 移動
  for nex,d in graph[now]:
    if used[nex]: #一回到達した頂点は考えなくていい
      continue
    else:
      used[nex] = True
      if pre == d:
        heappush(q,(t,d,nex))
      else:
        heappush(q,(t+1,d,nex))

if ans < 0:       
  print(ans)
else:
  print(ans*K)