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

質問する

入力

1行目は、都市数N(N<=100)と道路数M(M<=200)と、M行の道路情報とを与える.
と料金(20以下の自然数).1番都市と2番都市がつながっている場合、料金は13です
麺「1 2 13」.

しゅつりょく

すべての都市からすべての都市に移動するために必要な最小費用を次のように出力します.
自分の費用は0です.i番頂点からj番頂点に到達できない場合、コストは「M」です.
に出力します.

正解を解く

flowershallアルゴリズム

二次元配列のすべての値は5000

に初期化された.

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

2.3中国語実施

ドアのk値が変化すると、一番上(3重がドア)のドアが2重に回転してドアになり、配列が更新されます.
i->k->jの場合

正しいコード

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=" ")

コメント

FloydWarshallアルゴリズムを無理に出すために、もう一度勉強しましょう.