2015
04-15

# Graph

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?

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.

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.

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

Case 1: 6
Case 2: 4
Case 3: impossible

 Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author 4613099 2011-09-16 19:38:13 Accepted 4034 140MS 308K 943 B G++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
int gp[105][105],n;
int work()
{
int flag=1,count=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++)
{
if(i==k||j==k)continue;
if(gp[i][j]>gp[i][k]+gp[k][j]&&gp[i][k]&&gp[k][j])
{
flag=0;
return -1;
}
else
if(gp[i][j]==gp[i][k]+gp[k][j]&&gp[i][k]&&gp[k][j])
{
count++;
break;
}
}
}
return count;
}
int main()
{
int T,t,num;
scanf("%d",&T);
for(t=1;t<=T;t++)
{
num=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&gp[i][j]);
if(gp[i][j]!=0)num++;
}
printf("Case %d: ",t);
int tem=work();
if(tem==-1)
printf("impossible\n");
else
printf("%d\n",num-tem);
}
return 0;
}

,
1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

2. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。