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.

[cpp]
3
3
0 1 1
1 0 1
1 1 0
3
0 1 3
4 0 2
7 3 0
3
0 1 4
1 0 2
4 2 0
[/cpp]

#### Sample Output

[cpp]
Case 1: 6
Case 2: 4
Case 3: impossible
[/cpp]

#### #Source

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

#### Code

[cpp]
#include<bits/stdc++.h>
using namespace std;
#define clr(x,num) memset(x,num,sizeof(x));
#define Debug(x) cout<<#x<<” = “<<x<<endl;
typedef long long ll;
const int maxn = 1e5 + 7;
const int maxc = 1e3 + 5;
const int maxr = 1e5 + 5;
int g[maxc][maxc];
//有向图给出所有点之间的最短路要求还原图的最小边数
//通过Floyd更新去边
int _floyd(int n) {
int ans=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
if(i==j) continue;
for(int k=1; k<=n; k++) {
//比如 [1->3(12), 1->2(1), 1->3(2)]显然[1->3]这条边存在即不合理
if(i==k && j==k) continue;
if(g[i][j] > g[i][k] + g[k][j] && g[i][k] && g[k][j]) return -1;
else if(g[i][j]==g[i][k] + g[k][j] && g[i][k] && g[k][j])
{ans++;break;}
}
}
return ans;
}
int main() {
int t;scanf(“%d”,&t);
for(int kase=1; kase<=t; kase++) {
int cnt=0, n; scanf(“%d”,&n);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) {
scanf(“%d”,&g[i][j]);
if(g[i][j]) cnt++;//记录有效总边数
}
printf(“Case %d: “,kase);
int deleted = _floyd(n);
if(deleted == -1) printf(“impossible$n”); else printf(“%d$n”,cnt-deleted);
}
}
[/cpp]

This site uses Akismet to reduce spam. Learn how your comment data is processed.