[백준] #1389번 Floyd Warshall Algorithm python
2022. 11. 22. 08:42
https://www.acmicpc.net/problem/1389
Floyd Warshall Algorithm 을 이용하여 구현하였다.
import sys
INF = sys.maxsize
N, M = map(int, input().split())
s = [[INF] * N for i in range(N)]
for i in range(M):
num1, num2 = map(int, input().split())
s[num1 - 1][num2 - 1] = 1
s[num2 - 1][num1 - 1] = 1
for k in range(N):
for i in range(N):
for j in range(N):
s[i][j] = min(s[i][j], s[i][k]+s[k][j])
result = sys.maxsize
for i in range(N):
sum = 0
for j in range(N):
sum += s[i][j]
if result > sum:
result = sum
p = i
print(p + 1)
'Programming > Algorithm' 카테고리의 다른 글
[백준] #1463번 Dynamic Programming python (0) | 2022.11.26 |
---|---|
[백준] #12865번 Dynamic Programming python (0) | 2022.11.25 |
[백준] #2252번 Topological Sorting python (0) | 2022.11.21 |
[백준] #6096번 Max Flow python (0) | 2022.11.21 |
NetWork Flow Algorithm (네트워크 플로우) (0) | 2022.11.17 |