[白俊1956 Python]スポーツ(Gold 4,FloydWarshall)

9836 ワード
自由戦争 パイ ps アルゴリズム#アルゴリズム# 最短パス 白駿 コーディングテスト テキストリンク
アルゴリズムタイプ:floyd-walsh(最短パス)
草は参考にならずに自分で解いたのか.△
https://www.acmicpc.net/problem/1956

ソースコード(Python)

import sys
import heapq
input = sys.stdin.readline
INF = float('inf')

V, E = map(int, input().split())
APSP = [[INF]*(V+1) for _ in range(V+1)]

for i in range(1, V+1):
    APSP[i][i] = 0

for _ in range(E):
    a, b, c = map(int, input().split())
    APSP[a][b] = c

# 플로이드-워셜 알고리즘
def floyd_warshall():
    for mid in range(1, V+1):
        for start in range(1, V+1):
            for end in range(1, V+1):
                cal_dist = APSP[start][mid] + APSP[mid][end]
                
                if cal_dist < APSP[start][end]:
                    APSP[start][end] = cal_dist
    return APSP

APSP = floyd_warshall()

result = INF
# 모든 노드에 대해 최단 사이클 구하기
# 사이클을 구하는 방법은, 예를 들어
# 1에서의 사이클을 구하고 싶다면
# 1의 인접 노드 a, b, c로 이동한 다음
# a, b, c에서 1까지 최단 거리로 이동한다.
# 1 -> a - > 1, 1 -> b -> 1, 1 -> c -> 1
# 이 중 최솟값이 1에서의 최단 사이클이다.
# 이런 식으로 모든 노드들에 대해 수행해주는 것이다.
for c_villege in range(1, V+1):
    for adc_villege in range(1, V+1):
        if c_villege != adc_villege:
            cycle = APSP[c_villege][adc_villege] + APSP[adc_villege][c_villege]
            result = min(result, cycle)

if result >= INF:
    print(-1)
else:
    print(result)
プールの概要

  • floyd-walshアルゴリズムで解く場合は、pypy 3をコミットする必要があります.複数のExtraを利用して解答することもでき、より長い時間がかかるので時間の複雑さを比較し、複数のExtraノードの数で実行する必要があるため、2 VelogV、問題の条件下でEの範囲はV^2-V、およそVと3 logVである.フロイド・ウォーシェルはV^3ですが、このように比較すると、もっと長い時間のクローズアップが必要です.
    複数に変換してpython 3を通過する解があり、この解は検索で他のブログで参照できます.
  • まずfloydwashillでAPSPリストを取得する.

  • たとえば、1～サイクル、2～サイクル、3～サイクルのすべての値を求め、最小値を出力する必要があります.
    1の中の周期を求めます.
    周期を求める方法は,1から隣接ノードPに移動し,さらに隣接ノードから1までの最短距離値を加算する.
    すなわち,1におけるループ値が1を示す隣接ノードはa,b,cである.
    1 -> a -> 1
    1 -> b -> 1
    1 -> c -> 1
    これはその中の最高価格です.

  • この操作は、すべてのノードペアに対してデュアルfor文で実行することで、グラフィック全体の最短サイクルを見つけることができます.
    これは,隣接ノードでないノードの最短距離値がINFであればcycle値を更新する際にmin関数を取ることができるため,正しい値が正常に使用できるためである.
    • 勉強するところ、難しいところ
  • フロイド・ウォーシェルアルゴリズムが曖昧であるため,概念を再探求した.まだ経験が足りないようです.
    • 構造サイクロトロン行列
    JAVA固有文字の検索、フラクチャ、または追加