[伯俊]1753最短距離py

質問リンク:https://acmicpc.net/problem/1753

💡 アイデア

どのような方法で問題を解決したいかを書いてください.初期メソッドと最終メソッドに差がない場合、少なくとも1つのメソッドを使用することができる.

初期アクセス

で最初に作成されたコードはこうです.

V, E = map(int, input().split())
K = int(input())

# 충분히 큰 수로 배열 초기화
arr = [[int(1e9) for i in range(V+1)] for i in range(V+1)]

for i in range(E):
    a, b, c = map(int, input().split())
	  arr[a][b] = c # 주어진 위치에 dist 값 넣어줌

# 자기 자신의 거리는 0으로 설정
for i in range(V+1):
    arr[i][i] = 0

for i in range(1, V+1):
    key = arr[K][i]
    if key==0: # 자기 자신을 가리키는 경우 그냥 끝냄
        print(key)
        continue
    
    for j in range(1, V+1): # 거쳐가는 길 확인
        if arr[j][i] < key: # 거쳐가는 길을 기준으로 원래보다 크면 걍 지나침
            temp = arr[K][j] + arr[j][i] # 거리 새로 초기화
            key = min(temp, key)
    
    print(key)

2 D配列にstart、end、distanceの内容を記録する

行ごとに開始点をチェック

自分を指すと出力して終了します

本人の道を通ることを基準に新たな探索を行う.
(1-3-2で通過したい場合は、3を基準にナビゲーション(カラムナビゲーション)を行います.
3入ってきた子供たちは誰ですか.

新しく探した道が以前見つけた道よりもっと悪いとしたら、そのまま過ぎてしまいます.

新しい探求の道で新しい距離を計算する

小さい値を最終値とし、以前の距離と新しい距離と比較します.

でもそうするとメモリがオーバーします.質問を検索し始めたら2次元配列だったのですが、2万個入ってくると大きくなってしまい、、、
[白俊/python]1753-最短経路

最終アクセス

だから、、、、Dijkstraアルゴリズムが頑張って説明してくれた羅東彬のブログを、もう一度見てみました.

23.Dijkstraアルゴリズム

は羅東彬が実現したC++コードをPythonに直接変換したと言ってもいいだろう.アルゴリズムは本当にDijkstraの定式化です相変わらずです.

Pythonで初めて優先度Qを使用...検索済み

Pythonの優先キューの使用方法

もし私がtupleの形で入れたら....ソートすると一番前の値に基づいて優先順位キューが生成されるそうです.だから真ん中...私が最初に入れた時はheappush(pq、(K,0)の形で入れて、heappush(pq,0,K)の形に変えて入れました.距離で並べ替えるから!

ここまでやったのに、、、ずっとタイムアウト...だから念のため!このpriorityqueueは間違っていますか?質問を検索したいのですが、、、、次の人のようにheapqに変えて解答します.フォーマットをpriorityqueueからheapqに変更しただけで、他は変更されていません.

記事を読む-1753 Python実施タイムアウト

でもタイムアウト!!!1が出た・・・・だから、、、やっているうちにうんざりしてふたをして、、、子供たちと近づいたとき、私は私のコードを一つ一つ分解しました(かもしれません)

猛進...heappush(pq,(-next dist,next vert))ここには-が必要ですか?そう言いました.私はただ罗东彬の言うとおりにしただけです...だから-取り除いてもう一度やればいいのに...私の正解率はどうすればいいのか.

だから考えてみましたが、参考にしたあの質問掲示板の人もheapqと書いていましたが、書いていません...これは…です.これはPythonとCppの違いのようです.

Pythonのheapqは最小hip,cppのpriority queueは最大hip

最初はpythonでは昇順、cppでは降順!私が書いたとき、孟が本当に直してくれたと言った.

とにかく、だからPythonでは-処理する必要はありません......熱い...熱い...熱い・・・

[python]heapqモジュールの使い方

📋 使用仕様

どんなアルゴリズムやテクニックで問題を解決したか教えてください.

最小スタック

graph

Dijkstra

👨🏻‍💻 👩‍💻 コード#コード#

from heapq import heappush, heappop
# 시간 줄이기 위해서...
import sys
input = sys.stdin.readline

V, E = map(int, input().split())
K = int(input())

arr = [[] for i in range(V+1)]  # 입력받은 내용 저장할 배열

for i in range(E):
    a, b, c = map(int, input().split())
    arr[a].append((b, c))   # 인접 리스트 형식? a 자리에 (end vertex, distance) 형태로 저장
    
res = [int(1e9) for i in range(V+1)]    # 큰 값으로 최종 계산한 거리 배열 초기화
pq = []
heappush(pq, (0, K))    # python에서의 최소힙에 (distance, vertex) 형태로 저장

res[K] = 0  # 나!는 최단거리가 0이지~
while pq:
    dist, vertex = heappop(pq)  # 힙에서 하나씩 빼오기

    if res[vertex] < dist:  # 만약 저장된 거리가 충분히 작으면 걍 넘김
        continue

    for next_vert, d in arr[vertex]:    # 그 다음의 vertex와 거리 받아오기
        next_dist = d + res[vertex] # 새로운 거리 계산. 이전에 저장된 내용에 새로운 거리 더해서 새로운 루트? 만들어냄

        if next_dist < res[next_vert]:  # 새로 만든 방법? 루트가 더 짧으면
            res[next_vert] = next_dist  # update 시켜주고
            heappush(pq, (next_dist, next_vert))    # heap에 넣어줌

# 출력
for i in range(1, V+1):
    if res[i] == int(1e9):
        print("INF")
    else:
        print(res[i])

足りないところ

ソリューションに近づく前に残念な部分を書いてください.ソリューションを参考にして、修正箇所を書いてください.ソリューションへのリンクを書いてください.実装がスムーズであれば、省略できます.

私はPython Manになるまでまだ遠いですね・・・・・・・・・・・・・・Python Manになった日まで・・・^^

学識

この問題で学んだことを書いてください.あるアルゴリズム,符号化方法,資料構造などを理解した.文法要素もいいです.あまり多くなければ省略できます.
いいえ、私の涙の採点状況を見てください.
最后に最初の和弦を作り直してもいいですか!!!でもだめです.