Маленькая шалость

시간 제한2초메모리 제한1024 MB

요약
가중 무방향 그래프에서 간선 하나를 제거했을 때 정점 1로부터의 최단 거리가 바뀌는 정점 수가 최대가 되도록 하고, 그 최대 개수를 출력한다.
난이도

보통10점 중 6점

유형
그래프, 최단 경로, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

Однажды ночью Аль решил пойти погулять. Во время прогулки пришельцу стало скучно, и он решил как-нибудь напакостить. А именно, увидев карту города, Альф решил перекрыть дорогу, причем не любую, а ту, после перекрытия которой кратчайшее расстояние от его дома до всех интересных мест города изменится у максимального числа интересных мест.

Город представлен в виде графа с nn вершинами. Дом Альфа находится в вершине с номером 11.

Выведите максимальное число вершин, расстояние до которых изменится после удаления одного ребра в графе.

입력

В первой строке входного файла дано число nn (1≤n≤3001 \le n \le 300) --- количество вершин. В следующих nn строках дано по nn чисел a_i,ja\_{i, j} (−1≤a_i,j≤100000-1 \le a\_{i, j} \le 100000) --- матрица смежности. Если ребро в графе отсутствует a_i,ja\_{i, j} = -1. Гарантируется, что a_i,ia\_{i, i} = 0, a_i,ja\_{i, j} > 0 если ii \ne jj.

출력

Выведите ответ на задачу.

예제1

  1. 예제 1

    입력
    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