문제
그래프의 지름이란, 그 그래프에서 임의의 두 점 사이의 최단 거리 중 최대를 말한다. 주어진 그래프에서 지름을 구하는 프로그램을 작성하여라.
입력
입력의 첫 행에는 그래프의 정점의 개수 N(1≤N≤100)이 주어진다. 이후 N 행에 걸쳐서 각 행마다 N 개씩의 정수가 주어진다. i행 j열에 위치한 정수는 i번 정점에서 j번 정점으로의 간선의 가중치이다. 만약 이 값이 -1이라면 해당하는 간선이 없다는 뜻이다. 각 가중치는 10^9 이하이며, 그래프의 간선에 방향성이 없으므로 i행 j열에 위치한 값과 j행 i열에 위치한 값은 같다. 주어진 그래프는 항상 연결 그래프이다.
출력
입력에 대해 한 행에 하나씩 그래프의 지름을 출력한다.
예제
4
-1 5 -1 -1
5 -1 5 -1
-1 5 -1 5
-1 -1 5 -1
15
로그인해야 코드를 작성할 수 있어요.