競プロ初中級者100問

JOI2014予選E タクシー

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

ダイクストラ法
幅優先探索

はじめに

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

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

問題

https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_e

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

注意

この問題をPythonで解こうとした場合、多くの実装ではPython3で解くとTLE、PyPy3で解くとMLEになってしまいます。それを回避するためには本質的ではない計算量の削減も必要です。他の言語で挑戦するか、どうしてもPythonで挑戦したい方はACされている方のコードを参考にしましょう。（かなり苦しみました）

ダイクストラ法の練習のためには、こちらの問題よりも下記の問題に取り組むことをオススメします。

JOI2016予選E ゾンビ島

  • ほぼ同様の問題です。こちらはPython3で問題なく通せます。

JOI2008予選F 船旅

  • 上の問題よりも簡単です。

GRL1A Single Source Shortest Path

  • さらに簡単です。AOJ(Aizu Online Judge)というサイトの問題です。ダイクストラ法の基礎を学びたければこちらも良いでしょう。

方針

基本的には、解説の通りに実装すれば良いです。

  • 町iから町jまでタクシーを途中で乗り換えることなく行けるかどうかを判定する
    • 幅優先探索
  • 町iから町jまでタクシーを途中で乗り換えることなく行ける場合，町iから町jにコストCiの辺があると考える
  • 単一始点最短経路を求める
    • ダイクストラ法

コード

こちらのコードを参考にしました

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月25日
  • 最終更新日：2020年5月8日