【pythonでABC191を解説】E - Come Back Quickly

問題概要

問題ページ

問題文

AtCoder 国には、町 \(1\) から町 \(N\) までの \(N\) 個の町と、道路 \(1\) から道路 \(M\) までの \(M\) 本の道路があります。
道路 \(i\) は町 \(A_i\) から町 \(B_i\) への一方通行で、通るのに \(C_i\) 分かかります。\(A_i = B_i\) かもしれませんし、同じ町の組を結ぶ道路が複数あるかもしれません。
高橋君はこの国で散歩をしようと考えました。ある町から出発し、\(1\) 本以上の道路を通り、出発した町に帰ってくるような経路を正しい散歩経路と呼ぶことにします。
各町について、その町から出発する正しい散歩経路が存在するかを判定してください。また、存在するなら、そのような経路を通るのにかかる時間の最小値を求めてください。

制約

• \(1 \le N \le 2000\)
• \(1 \le M \le 2000\)
• \(1 \le A_i \le N\)
• \(1 \le B_i \le N\)
• \(1 \le C_i \le 10^5\)
• 入力は全て整数

問題の考察

典型的なダイクストラ法の問題。

幅優先探索とダイクストラ法の使い分けは、とりあえず「辺の重み（移動コスト）があるかないか」と覚えておきましょう。

自己ループがある点だけ注意すれば、ほぼテンプレ通りで解ける。

自己ループへの対処として各始点をあらかじめ移動先のキューリストに追加しておけばよい。

こうすれば、自己ループが最短距離の場合もif now_edge == i:で拾えるので問題ない。

たびすけ

この問題を解くまでedgeの部分をlistで処理していましたが、tupleの方が倍以上速かったのでテンプレを変更しました。
（tupleの方が早いのは知っていましたが、ここまで違うとは思っていませんでした・・・）
この問題自体は基本的なダイクストラ法の問題です！

ACコード

import sys
import heapq


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    edge = [[] for _ in range(n)]
    for i in range(m):
        edge_a, edge_b, cost = list(map(int, input().rstrip('\n').split()))
        edge[edge_a-1].append((edge_b-1, cost))

    ans = [-1] * n
    fq = [-1] * n
    for i in range(n):
        ql = []
        heapq.heapify(ql)
        #ここで始点の移動先をキューリストに追加
        for next_edge, cost in edge[i]:
            heapq.heappush(ql, (cost, next_edge))
        while True:
            if len(ql) != 0:
                cost, now_edge = heapq.heappop(ql)
                if now_edge == i:
                    ans[i] = cost
                    break
                if fq[now_edge] < i:
                    fq[now_edge] = i
                    for next_edge, p_cost in edge[now_edge]:
                        heapq.heappush(ql, (cost + p_cost, next_edge))
            else:
                break
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()