e-olymp
Yarışlar

Azerbaijan Programming Olympiad - 2nd Stage preparation

Диаметр графа

Дан связный взвешенный неориентированный граф.

Рассмотрим пару вершин, расстояние между которыми максимально среди всех пар вершин. Расстояние между ними называется диаметром графа. Эксцентриситетом вершиныv называется максимальное расстояние от вершины v до других вершин графа. Радиусом графа называется наименьший из эксцентриситетов вершин.

Найдите диаметр и радиус графа.

Входные данные

В первой строке находится количество вершин графа n (1n100). В следующих n строках по n чисел - матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число - присутствие ребра данного веса. На главной диагонали матрицы всегда нули; веса рёбер не превышают 1000.

Выходные данные

Выведите два числа: диаметр и радиус графа.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4
0 -1 1 2
-1 0 -1 5
1 -1 0 4
2 5 4 0
Çıxış verilənləri #1
8
5