Maximizing Flight Efficiency
시간 제한0.5초메모리 제한1024 MB
도시 간 직항 비용 행렬이 주어질 때, 경유 경로가 직항보다 싼 경우가 있는지 확인하고, 없다면 없애도 되는 직항의 최대 개수를 구한다.
문제
In the kingdom of Quadradonia, the king wants to review the prices of flights. For this purpose, he asked his accountant for a table with proposals for new prices.
However, the king studied at the Institute of Computing and Programming of Chapec´o (ICPC) and has sufficient knowledge to demand coherence in the table. The table is considered coherent if no multi-stop route is cheaper than a direct flight.
Once the coherence of the table has been verified, the king would like to decrease the number of direct flights, without increasing the costs of the trips.
Your problem is to verify the coherence of the table and, if it is coherent, inform the king how many direct flights can be eliminated without increasing the cost of any trip.
입력
The first line of input contains an integer N (1 ≤ N ≤ 100), the number of cities in Quadradonia served by flights. Following there are N more lines, L1, L2, . . . , LN. Line Li contains N integers, Ci1, Ci2, . . . , CiN, where Cij is the cost of the direct flight between cities i and j.
The cost for an outbound and a return flight between two cities is always the same, meaning Cij = Cji for all pairs i, j where 1 ≤ i ≤ N and 1 ≤ j ≤ N. When i = j, Cij = 0. When i ≠ j, 1 ≤ Cij ≤ 103.
출력
Print a single line containing an integer. If the table is incoherent, the integer should be -1. If the table is coherent, the integer should be equal to the maximum number of direct flights that can be removed without increasing the costs of the trips for the passengers.