도현이는 현재 거대한 분산 처리 시스템의 네트워크 라우팅(Routing) 모듈을 최적화하는 작업에 골머리를 앓고 있습니다.

이 네트워크는 개의 서버와 서버들을 잇는 개의 양방향 광케이블 통신 링크로 구성되어 있으며, 각 링크마다 초당 전송할 수 있는 최대 데이터 양인 대역폭(Bandwidth)이 정해져 있습니다.

서버 A에서 서버 B로 데이터 패킷을 전송할 때, 전체 데이터의 전송 속도는 경로에 포함된 링크들 중 가장 작은 대역폭에 의해 병목(Bottleneck) 현상이 발생하여 결정됩니다. 따라서 대용량 데이터를 최대한 빠르게 전송하려면, 통신 가능한 여러 경로 중에서 병목 구간의 대역폭이 가장 큰 경로를 선택하여 라우팅해야 합니다.

어떻게 하면 수많은 쿼리에 대해 최적의 경로를 빠르게 찾을 수 있을지 끙끙대던 도현이에게, 여러분은 모니터에 띄워져 있던 플로이드 워셜(Floyd-Warshall) 알고리즘을 가리키며 무심하게 툭 던졌습니다.

"도현아, 플로이드 워셜에서 쓰이는 min이랑 + 연산자만 의미에 맞게 싹 바꾸면 풀리는 거 아니야?"

그 말을 들은 도현이는 무릎을 탁 치며 소리쳤습니다.

"와, 너 정말 핵심을 찔렀어!"

기본적인 플로이드 워셜 알고리즘은 모든 정점 쌍 사이의 최단 거리를 다음과 같이 구합니다.

for k from 1 to N:
  for i from 1 to N:
    for j from 1 to N:
      dist[i][j] ← min(dist[i][j], dist[i][k] + dist[k][j])

도현이의 네트워크 모듈에는 총 개의 데이터 전송 요청이 들어옵니다. 각 요청은 출발 서버 와 도착 서버 로 이루어져 있습니다.

도현이를 도와, 극찬을 받은 여러분의 아이디어대로 플로이드 워셜 알고리즘의 핵심을 변형하여 각 요청마다 에서 로 데이터를 전송할 때 확보할 수 있는 최대 통신 대역폭을 구하는 프로그램을 작성해 주세요.

(Python3로 제출 시 시간 초과를 받을 위험이 있으니 Pypy3로 제출하는 것을 권장합니다.)

#	Result	Memory
0	Accepted	0.01 MB
1	Accepted	0.01 MB
2	Accepted	0.01 MB
3	Accepted	0.01 MB

Submission #29126

Submission #29126

User

Result

Language

Submission Time