Part7.12動的プログラミング(Dynamic Programming)FloydWarshallアルゴリズム

質問する

入力

しゅつりょく

正解を解く

が最初に更新され、ディーゼルオイルを使わずに直行できます.

2.3中国語実施

正しいコード

import sys
sys.stdin = open ("input.txt", "rt")

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    #n 은 정점번호, m은 간선의 개수
    n, m = map(int,input().split())
    # 냅색 알고리즘과 동일한 원리이다.
    #경유지를 1부터 N까지 경유해서 가는 방법을 갱신한다
    dis=[[5000]*(n+1) for _ in range(n+1)]

    for i in range(1,n+1):
        dis[i][i] = 0 #대각선 0으로 초기화

    for i in range(m):#최초로 인접행렬로 초기화(아무 노드 거치지 않고 직행)
        a,b,c = map(int,input().split())
        dis[a][b] = c

    for k in range(1, n+1):# 프로이드 워샬 알고리즘
        # k기 바뀔때마다 아래 이차원리스트 갱신.
        for i in range(1,n+1):
            for j in range(1,n+1):
                dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j])
                # 다이나믹 테이블 값 갱신 i -> k -> j 를 거쳐서 간 최소값
                
        for i in range(1,n+1):
            for j in range(1,n+1):
                if dis[i][j] == 5000:
                    print("M", end=' ')
                else:
                    print(dis[i][j], end=" ")

コメント