| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 11 | 2 | 1 | 10.000% |
Однажды ночью Аль решил пойти погулять. Во время прогулки пришельцу стало скучно, и он решил как-нибудь напакостить. А именно, увидев карту города, Альф решил перекрыть дорогу, причем не любую, а ту, после перекрытия которой кратчайшее расстояние от его дома до всех интересных мест города изменится у максимального числа интересных мест.
Город представлен в виде графа с $n$ вершинами. Дом Альфа находится в вершине с номером 1ドル$.
Выведите максимальное число вершин, расстояние до которых изменится после удаления одного ребра в графе.
В первой строке входного файла дано число $n$ (1ドル \le n \le 300$) --- количество вершин. В следующих $n$ строках дано по $n$ чисел $a_{i, j}$ ($-1 \le a_{i, j} \le 100000$) --- матрица смежности. Если ребро в графе отсутствует $a_{i, j}$ = -1. Гарантируется, что $a_{i, i}$ = 0, $a_{i, j}$ > 0 если $i$ \ne $j$.
Выведите ответ на задачу.
5 0 16 12 1 12 16 0 12 13 -1 12 12 0 5 2 1 13 5 0 2 12 -1 2 2 0
4