トップページ -> AOJの解答例 -> ALDS1_12の解答例

ALDS1_12の解答例(Python)

最短経路に関する問題です．アルゴリズムについて詳しく知りたい方は参考文献などをご覧ください．

1. ALDS1_12_A: Minimum Spanning Tree

最小全域木の辺の重みの総和を求める問題です．言い換えれば，与えられた重み付きグラフの全ての点を通る木の中から辺の重みの総和が最小のものを探す問題です．優先度付きキューを使ってまだ辿り着いていない点への重みの小さい辺を順番に付け足していけば最小全域木が出来上がります．


# ALDS1_12_A
# 重みの小さい点から選び取っていく
import heapq
n = int(input())

A = []
for _ in range(n):
    a = list(map(int,input().split()))
    A.append(a)
    
w_list = [] # w_list[n] = ["点mへの辺の重み",m]
heapq.heapify(w_list)
# 始点から出ている辺の重みのリストを作る
for i,w in enumerate(A[0]):
    if w!=-1:
        heapq.heappush(w_list,[w,i])
        
weight = 0
done_set = set([0]) # 既に到達した点の集合
while len(done_set)!=n: # すべての点に到達するまでループ
    w,i = heapq.heappop(w_list) # 重みの小さい点から取り出す
    if i not in done_set:
        done_set.add(i)
        weight += w
        for j,w in enumerate(A[i]):
            if w!=-1:
                heapq.heappush(w_list,[w,j]) # 経路があれば追加する
                
print(weight)

2. ALDS1_12_B: Single Source Shortest Path I

単一始点最短経路に関する問題です．点0からある点への最短経路の重みを求める問題です．頂点と辺の数が少ないので単純に既に見つかっている最短経路と新しく見つかった経路を比較し，短くなった場合はもう一度調べなおすだけで間に合います．最悪の場合は100個の頂点が全て辺でつながっているときですが，最悪でも1ステップで1頂点ずつ最短経路が見つかって確定していくのでwhileループの処理は50万回程度で済みます．


# ALDS1_12_B
n = int(input())

adj_array = []
for i in range(n):
    u = list(map(int,input().split()))
    u,k,adj_list = u[0],u[1],u[2:]
    
    adj_array.append(adj_list)
    
# 0を始点とした時の最短経路
point_list = [0]
cost_dict = {i:float("inf") for i in range(n)} # 最短経路は無限で初期化しておく
cost_dict[0] = 0 # 始点はコスト0
while point_list:
    p = point_list.pop()
    
    adj = adj_array[p]
    for i in range(0,len(adj),2):
        u,c = adj[i],adj[i+1]
        # 既に見つかっている最短経路と新しく見つかった経路を比較する 短くなった場合はもう一度調べなおす
        if cost_dict[p]+c < cost_dict[u]: 
            cost_dict[u] = cost_dict[p]+c
            point_list.append(u)
            
for i in range(n):
    print(i,cost_dict[i])

3. ALDS1_12_C: Single Source Shortest Path II

Bと全く同じ問題ですが，頂点と辺の数が大幅に増えているため同じコードでは通りません．最短経路の分かっている点(初めは始点のみ)から行くことのできる全ての点のうち重みが最小の点は最短経路で確定するので優先度キューを使って順番に処理することで既に確定した点に関しての処理を省略します．ダイクストラ法とかdjikstra法で検索すると分かりやすい説明が出てくるかもしれません．
【外部サイト】ダイクストラ法とは？


# ALDS1_12_C

# 点0は0コスト 点0から出ている辺の重みが最小の辺は最短経路で確定
# 点を調べたら ある点までの重み と その点から出ている重みが最小の辺の重みの和 で優先度を付けて優先度キューに点を追加する
# 次に優先度キューから取り出されるのは 確定している点から行ける最も近い点なので最も近い点への最短経路が見つかる(近い点から順に最短経路が確定していく)

import heapq
n = int(input())

adj_array = []
for i in range(n):
    u = list(map(int,input().split()))
    u,k,adj_list = u[0],u[1],u[2:]
    
    adj_array.append(adj_list)
    
# 0を始点とした時の最短経路
# 次の辺への最小コストと現在のコストの和 始点 現在の最短経路 
adj = adj_array[0]
point_list = [[adj[2*i+1],0,adj[2*i]] for i in range(len(adj)//2)] # [重み 始点 終点]のリスト

heapq.heapify(point_list)
cost_dict = {i:float("inf") for i in range(n)} # 最短経路は無限で初期化しておく
cost_dict[0] = 0 # 始点はコスト0
done_set = set([0])

# 近いところから順に確定させていく
while point_list:
    c,u,v = heapq.heappop(point_list) # 最短経路が確定している点からの行ける点のうち重みが最小の点(最も近い点)を取り出す
    
    if v not in done_set:
        cost_dict[v] = c # 確定している点から最短で行ける経路なので最短経路

        adj = adj_array[v] # vから行ける点の重み付き隣接リスト
        done_set.add(v) # 確定済みに追加
        for i in range(0,len(adj),2):
            # vから行ける点が確定済みでなければpoint_listに追加
            if adj[i] not in done_set:
                heapq.heappush(point_list,[adj[i+1]+c,v,adj[i]])
            
for i in range(n):
    print(i,cost_dict[i])

<- 前へ戻る【目次に戻る】次へ進む ->