未来の都市

1297 ワード

イコテコセット最短パスりゅうすいアルゴリズムこれがコードテストですアルゴリズム#アルゴリズム# 未来の都市テキストリンク

今日解決すべき問題は~~

この問題です.自分で読んでほしいな~
結論は1号会社からx社に行くことになり、その前にk号会社を訪問することになります.
質問に答えてみれば

n, m = map(int, input().split()) #n,m을 입력받고
INF = int(1e9) # 무한대 설정하고
graph = [[INF]*(n+1) for _ in range(n+1)] # 그래피를 그리고
#
for _ in range(m): #연결된 회사 입력 받기
  a,b = map(int, input().split())
  graph[a][b] = 1

for i in range(1, n+1):
  for a in range(1 ,n+1):
    for b in range(1, n+1):
      test1[a][b] = min(test1[a][b], test1[a][i]+test1[i][b]) 
#플로이드 알고리즘으로 거쳐가는 노드를  제외하고 모든 노드를 다 조사해준다

その結果は.