クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-5 Roadblocks（POJ No.3255）」(p.102)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-5 Roadblocks（POJ No.3255）」(p.102)
のコードをPythonで書き直したものとなっています。

入力


N:交差点の数\\R:道の本数\\交差点s_iと交差点t_iの間に長さc_iの道が存在する(1\leq{i}\leq{R})


N\,R\\s_1\,t_1\,c_1\\:\\s_R\,t_R\,c_R

入力例



4 4
1 2 100
2 3 250
2 4 200
3 4 100


解答

# 優先度付きキューをインポートする
import heapq

MAX_N = 5000
MAX_R = 100000
INF = float('inf')

# 入力
N, R = map(int,input().split())
G = [[] for _ in range(MAX_N)]    # グラフの隣接リスト表現
for i in range(R):
    s, t, c = map(int,input().split())
    G[s-1].append([t-1, c])
    G[t-1].append([s-1, c])

que = []
dist = [INF] * MAX_N     # 最短経路
dist2 = [INF] * MAX_N    # 二番目の最短経路
dist[0] = 0
heapq.heappush(que, [0, 0])

while len(que) != 0:
    p = heapq.heappop(que)
    d = p[0]
    v = p[1]
    if dist2[v] < d:
        continue
    for i in range(len(G[v])):
        e = G[v][i]
        d2 = d + e[1]
        if dist[e[0]] > d2:
            dist[e[0]], d2 = d2, dist[e[0]]
            heapq.heappush(que, [dist[e[0]], e[0]])
        if dist2[e[0]] > d2 and dist[e[0]] < d2:
            dist2[e[0]] = d2
            heapq.heappush(que, [dist2[e[0]], e[0]])
print(dist2[N - 1])