srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

atcoder

CODE THANKS FESTIVAL 2015 G - カメレオン

問題 問題概要 頂点1からNまでの最短コストを求めよ. ただし辺のコストtに加えて, 辺を通る時の色が決められているので, 色を変えるのにもコストがかかる. xからyに色を変える場合のコストは, |x-y|である. 解法 拡張ダイクストラをすればいい. dist[i][j]と…