# HDU 4034 Graph

/ 0评 / 0

Time Limit: 2000/1000 MS (Java/Others)

#### Problem Description

Everyone knows how to calculate the shortest path in a directed graph. In fact, the opposite problem is also easy. Given the length of shortest path between each pair of vertexes, can you find the original graph?

#### Input

The first line is the test case number $T (T ≤ 100)$.
First line of each case is an integer$N (1 ≤ N ≤ 100)$, the number of vertexes.
Following N lines each contains N integers. All these integers are less than $1000000$.
The jth integer of ith line is the shortest path from vertex $i$ to $j$.
The ith element of ith line is always 0. Other elements are all positive.

#### Output

For each case, you should output “Case k: ” first, where k indicates the case number and counts from one. Then one integer, the minimum possible edge number in original graph. Output “$impossible$” if such graph doesn't exist.

#### #Source

The 36th ACM/ICPC Asia Regional Chengdu Site —— Online Contest

• 默认
• 护眼
• 夜晚
• Serif
• Sans