Courses

그래프 이론

플로이드 알고리즘

Module: 플로이드 알고리즘

Problem

3 /10

가장 긴 방법

Problem

가장자리에 음수가 아닌 가중치(길이)가 할당된 유향 그래프가 있습니다. 길이가 가장 긴 최단 경로인 두 정점을 찾아야 합니다.

입력

첫 번째 줄에는 N≤50의 꼭지점 수가 포함됩니다. 다음은 그래프의 인접 행렬, 즉 각각 N개의 숫자를 포함하는 N개의 행입니다. 인접 행렬의 i번째 행의 j번째 숫자는 i번째 꼭지점에서 j번째 꼭지점까지 이어지는 가장자리의 길이를 지정합니다. 길이는 0에서 1000000 사이의 값을 가질 수 있습니다. 행렬의 주 대각선에 0이 있음을 보장합니다.

출력

단일 숫자 인쇄 – 원하는 경로의 길이.

예 <헤드> <일># <몸>

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking