[白俊11403]道を探せ❗
5095 ワード
https://www.acmicpc.net/problem/11403
🥚質問する
i番ノード->k番ノード->j番ノードのパス を確認します.
第の問題において、経路が存在する場合は(i,j)直接接続、(i,k)->(k,j) パスが存在する場合、値は1に更新されます.
🥚質問する
🥚入力/出力
🍳コード#コード# import sys
input = sys.stdin.readline
n = int(input().strip())
g = [list(map(int, input().split())) for _ in range(n)]
# Floyd Warshall
# i -> k번 노드 -> j 로 거쳐가는 경로를 확인한다
for k in range(n):
for i in range(n):
for j in range(n):
if g[i][j] == 1 or (g[i][k] == 1 and g[k][j] == 1):
g[i][j] = 1
"""
어차피 g[i][j] = 1로 갱신하기 때문에
사실 g[i][j] == 1인 경우는 검사 안하고 넘어가도 됨
그러나 이해를 위해 if문에서 검사하기로!
"""
# 출력
for row in g:
for x in row:
print(x, end=' ')
print()
🧂アイデア
Floyd-Warshallアルゴリズム
🍳コード#コード# import sys
input = sys.stdin.readline
n = int(input().strip())
g = [list(map(int, input().split())) for _ in range(n)]
# Floyd Warshall
# i -> k번 노드 -> j 로 거쳐가는 경로를 확인한다
for k in range(n):
for i in range(n):
for j in range(n):
if g[i][j] == 1 or (g[i][k] == 1 and g[k][j] == 1):
g[i][j] = 1
"""
어차피 g[i][j] = 1로 갱신하기 때문에
사실 g[i][j] == 1인 경우는 검사 안하고 넘어가도 됨
그러나 이해를 위해 if문에서 검사하기로!
"""
# 출력
for row in g:
for x in row:
print(x, end=' ')
print()
🧂アイデア
Floyd-Warshallアルゴリズム
import sys
input = sys.stdin.readline
n = int(input().strip())
g = [list(map(int, input().split())) for _ in range(n)]
# Floyd Warshall
# i -> k번 노드 -> j 로 거쳐가는 경로를 확인한다
for k in range(n):
for i in range(n):
for j in range(n):
if g[i][j] == 1 or (g[i][k] == 1 and g[k][j] == 1):
g[i][j] = 1
"""
어차피 g[i][j] = 1로 갱신하기 때문에
사실 g[i][j] == 1인 경우는 검사 안하고 넘어가도 됨
그러나 이해를 위해 if문에서 검사하기로!
"""
# 출력
for row in g:
for x in row:
print(x, end=' ')
print()Floyd-Warshallアルゴリズム
第
Reference
この問題について([白俊11403]道を探せ❗), 我々は、より多くの情報をここで見つけました https://velog.io/@eastgloss0330/백준-11403-경로-찾기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol