ABC192 E Train ~Dijkstraの実装でハマった話~

#はじめに
　本記事は競技プログラミングにおいて解くのに困った問題について、なぜその解法に思い至るのか、どのような所でハマったか等のポイントをメモした、筆者の筆者による筆者のための備忘録となっております。読まれることを意識していないので文章がとっ散らかってます。

#問題
問題はこちら。

概略
　$N$個の頂点と$M$本の辺からなる無向グラフがある。辺$i$は頂点$A_i, B_i$を結んでおり、この間の移動には$T_i$の時間を要する。ただし時刻が$K_i$の倍数である時のみこの辺の移動を開始できる。
　頂点$X$を時刻0に出発して頂点$Y$に到達するまでの最短時間を求めよ。　

#提出解答
提出解答はこちら。

ABC192E.py

from heapq import heappush, heappop, heapify
n, m, x, y = map(int, input().split())
path = [[] for _ in range(n)]
for _ in range(m):
    a, b, t, k = map(int, input().split())
    path[a-1].append((b-1, t, k))
    path[b-1].append((a-1, t, k))

s, g= x-1, y-1

INF = 2*10**14+1
def dijkstra(s, n):
    hq = [(0, s)]
    heapify(hq)
    d = [INF]*n
    d[s] = 0
    decided = [0]*n

    while hq:
        l, v = heappop(hq)
        if decided[v]:
            continue 
        decided[v] = 1
        for nv, t, k in path[v]:
            if decided[nv]:
                continue
            d[nv] = min(d[nv], (d[v] + k-1)//k*k + t)
            heappush(hq, (d[nv], nv))
    return d

d = dijkstra(s, n)
if d[g] == INF:
    print(-1)
else:
    print(d[g])

#Dijkstra法って？
　Dijkstra(ダイクストラ)法とは、グラフ中のある1点から他の全ての頂点までの最短経路を求めるアルゴリズムです。使える条件は、各辺の重みが非負である時です。重みが負の時はベルマンフォード法というものがあるらしいですが良く勉強していないので口を閉じます。
　さて、手順は以下の通りです。

1. $d[v]$をすべてINFで初期化し、始点$s$について$d[s]=0$とする。
2. まだ距離が確定していない頂点の内、$d[v]$が最小である$v$をとり、$d[v]$を確定する。
3. $v$から到達できる点であり、距離が確定していない点$nv$について、$d[nv] = min(d[nv], d[v]+|e(v, nv)|)$と更新する。

4.距離が未確定の頂点が残っているならば2に戻る。

　上記のようにして作った$d[v]$が$s\to v$の最短距離となります。ちなみに$d[nv]$の更新の際に、「$nv$の前は$v$にいた」という情報を保存することで、最短距離のみならず具体的な最短経路も復元することができるらしいです(今回はしていません)。
　計算量を見積もりましょう。2~4を1回しすると必ず頂点が1つずつ確定していくため、2~4は$|V|$回繰り返されます。ここで2を行う際、線形探索を行うならばこれは$|V|$回かかるため、全体の計算量は$O(|V|^2)$となります。一方で未確定の頂点を**優先度付きキュー(プライオリティキュー、ヒープキューとも言う)**で管理することで、全体の計算量を$O(|E|\log{|V|})$にすることが可能なようです(計算量の導出の理解はとりあえず諦めました)。頂点と辺の個数によって2つの手法を使い分けると良いらしいです(グラフが相当密、すなわち$|E|\simeq |V|^2$でない限りは後者が良い気がします)。

　それでは次項より、実装で主にハマった2つの点について話していきます。

#確定した頂点を管理する配列でハマった
　私は"頂点$v$の最短経路が確定しているか否か"を配列$decided[v]$で管理しました。当然$decided[v] = 1$なる頂点$v$についての処理はcontinueでスキップするわけですが、2において$v$をヒープキューから取り出した際にはその処理を行いませんでした。冒頭に載せた提出解答のコメントアウトしている部分です。
　一応根拠はあります。ヒープキューは最短経路が未確定の頂点($d[v]$=INFなる頂点、すなわち未更新の頂点は除く)を格納しているキューでした。故にそのキューに含まれる頂点は全て$decided[v]=0$なのではないかと考えていました。

　しかしここで失念していた状況があります。それは、1つの頂点$v$が未確定の状態で複数の経路からヒープキューに格納されるような場合です。そのような場合、頂点$v$を取り出してきて距離を確定、すなわち$decided[v]=1$とすると、ヒープキュー内に$decided[v]=1$となっている頂点が含まれてしまうことになります。このような頂点を何度も取り出してきてしまってはおかしくなっています。

　これに気づかずTLE,WAを連発して首を傾げまくって首が痛くなりました。養生します。

#INFの値の設定でハマった
　INFの設定を問題ごとにしっかり考えることはとても大切なことです。そこをかなり適当にやってしまい、WAを連発してこれまた首を傾げていました。今回のINFの値として適切な数字を見積もっていきましょう。

　考えるべきは、頂点$X$から他の頂点$v$まで最大でどれほど時間がかかるか、です。まずグラフの形状は道(頂点が一直線上に並んでいるようなグラフ)であるとし、その両端に$X, v$が位置する時が一番時間がかかるでしょう。
　次に移動にかかる時間について考えましょう。各頂点の間を移動するのには$T_i$だけ時間がかかります。今回は移動時間に加え、待ち時間も考えなければなりません。時刻が$K_i$の倍数になった時に移動できるわけですが、$K_i$の倍数は自然数の上で$K_i$ごとに現れるので、待ち時間は最長で$K_i-1$となります。よってある2頂点間を移動するのにかかる時間は最長で$T_i+K_i$程度となります。
　$X\to v$の移動中に辺は$N-1$本あるため、この行動が$N-1$回行われ、全部でだいたい$\sum_i(T_i+K_i)$程度の時間がかかります。

　さて、この値はどれくらいの数字で抑えられるでしょうか。制約に注意してみると、
$$\sum_i(T_i+K_i) \leq \sum_i(10^5+10^5)$$
$$=2\times10^5\times N \leq 2\times10^{14}$$

となります。よってINFの値としては$2\times 10^{14}$よりも大きい値を設定すれば問題ないでしょう。実際冒頭の提出解答ではINF$=2\times10^{14}+1$としています。試しこれよりもINFの値を小さくしてみた解答がこちらです。ちなみに$2\times 10^{14}-1$程度ではまだ大丈夫でした。
　これで無事にACすることができました。

#反省

• 人生で初めてDijkstraを使った。授業でアルゴリズムを聞きかじった程度だったのでいい経験になった。
• ACするまでに数日だらだらと時間をかけてしまった。他の用事があったのもあるが、ちょっとずつ早くインプットできるようにしたい。
• ヒープキューにタプルを入れるとき、どうやらノードの大小関係はタプルの第0成分で判定されるっぽい。なので(経路長, 頂点名)の順にしないと落ちそう。
• 首を労わりたい。