OI题库

一张磁盘被写入了一张公路网。这张磁盘包括一个写有任何两个村庄之间最短路径长的表格。所有的路都是双向的。地图上的村庄所处的位置有以下一个有趣 的特点：如果村庄A与村庄B之间的最短路径长等于村庄A与村庄C之间的最短路径长和村庄B与村庄C之间的最短路径长之和，我们就说村庄C处在村庄A与村庄 B的最短路径上。如果不存在其他的C使村庄C在村庄A与村庄B的最短路径上，我们把村庄A、B称为相邻的村庄。试找出所有的相邻村庄。

例子： 对于如下一张距离表格：

  A B C
A 0 1 2
B 1 0 0
C 2 3 3

相邻的村庄有村庄A和B，A和C。

任务： 编一个程序：

• 从文件中读入最短距离表格。
• 找出所有的相邻村庄。
• 把结果写入文件。

输入： 在文件的第一行有一个整数n(1<=n<=200)表示地图中村庄的个数，村庄被标号为1..n。

以下n行给出最短距离表格，在第i+1行(1<=i<=n)有n个非负整数(不超过200)，有空格隔开，第j个整数表示村庄I与j的最短距离。

输出：

你的程序必须在文件中给出所有的相邻村庄对。每行写一对，每一对只出现一次。每一对中的数字必须升序给出，且当对(a,b)与(c,d)满足（a

输入样例：

3
0 1 2
1 0 3
2 3 0

输出样例:

1 2
1 3