白駿1753号最短経路(Python)

[ソース]:https://www.acmicpc.net/problem/1753
問題の核心はダエストラの最短経路です!
1つの頂点からすべての接続された頂点までの最短距離を検索するアルゴリズム.
floydアルゴリズムとshallアルゴリズムは、頂点ではなくすべての頂点を決定することができます.

解法

各ノードに移動する際のコストを格納する変数を定義します->cost_list

cost_list友人の要素は最低価格で初期化(最短距離だから!)pythonは最長~~~~値をfloat('inf')と表すことができ、逆にfloat('-inf')に設定すると最長~~を表すことができる.

cost_listの開始インデックスは0として定義される.

最初のノードに関連する値を順次ループし、より小さい値に更新します.

heapqを使用して、リスト内の最高価格を見つけることができます.

source code

import heapq, sys
input = sys.stdin.readline

node_len, road_len = map(int, input().split())
start = int(input())
node_info = [[] for _ in range(node_len+1)] # index 0 무시하기 (node개수의 +1)
for _ in range(road_len):
    s, e, w = map(int, input().split())
    node_info[s].append((e, w)) # next_node, next_cost => 아래 [1]번에서 쓰임

cost_list = [float('inf')] * (node_len+1) # 전체 노드를 무한대로 초기화
cost_list[start] = 0 # 시작값 초기화

check = []
heapq.heappush(check, (0, start)) # curr_cost, curr_node
while check:
    curr_cost, curr_node = heapq.heappop(check) # check안의 최소값 반환
    for next_node, next_cost in node_info[curr_node]: # => 위에 말했던 [1]번
        if curr_cost + next_cost < cost_list[next_node]:
            cost_list[next_node] = curr_cost + next_cost # 작은 값으로 갱신
            heapq.heappush(check, (cost_list[next_node], next_node))
for x in cost_list[1:]:
    print(x if x != float('inf') else 'INF') # inf가 그대로면 INF, 아니면 원래값 반환

IDEでテストケースをデバッグする際の秘訣...

処理

のルートディレクトリに任意(input.txt)のテキストファイル

を作成する.
生成されたテキストファイルにテストキャビネット

を貼り付ける

ソースコード上部のsysライブラリインポートポート

以降のsys.stdinに、作成したファイルを割り当てますか?夏至

# ex)
import sys
sys.stdin = open('input.txt', 'rt') # input.txt파일을 읽는다('rt')

というと!runボタンを押すだけで

を起動できるようになりました.