競プロ初中級者100問

JOI2008予選F 船旅

この記事で使うアルゴリズム

ダイクストラ法

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_f

この問題はダイクストラ法を用いて解くことができます。

ポイント

ダイクストラ法は優先度付きキューを用いることで高速化できます。

Pythonで優先度付きキューを実装する際は、標準ライブラリのheapqを利用すると良いでしょう。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import heapq
INF = 10**10

def dijkstra(s, g):
    dists  = [INF for i in range(N)]
    dists[s] = 0
    pq = [(0, s)] # 優先度付きキューのオブジェクトそのものはただのリスト
    while(pq):
        d, node = heapq.heappop(pq)
        if (d > dists[node]): # 探索の対象にする必要があるか確認
            continue
        for next, cost in adj[node]:
            if d + cost < dists[next]: # 更新すべきか確認
                dists[next] = d + cost
                heapq.heappush(pq, (dists[next],next))
    if dists[g] == INF:
        return -1
    else:
        return dists[g]

N, K = map(int,input().split())
adj = [[] for i in range(N)]
ans = []
for k in range(K):
    ls = list(map(int,input().split()))
    if ls[0]==0:
        ans.append(dijkstra(ls[1]-1, ls[2]-1))
    else:
        adj[ls[1]-1].append((ls[2]-1,ls[3]))
        adj[ls[2]-1].append((ls[1]-1,ls[3]))
for a in ans:
    print (a)

記事情報

  • 投稿日：2020年4月23日
  • 最終更新日：2020年5月8日