POI 1998 公路网 Road net
非常简单的枚举,三重循环。对于每一个城市对,枚举中间城市,如果中间有城市,则不是“相邻城市”,否则就是,输出即可。
/*
* Problem: POI1998 sie
* Author: Guo Jiabao
* Time: 2008.11.29 21:22:22
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAX=201;
int dis[MAX][MAX];
int N;
void init()
{
int i,j;
freopen("sie.in","r",stdin);
freopen("sie.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
{
for (j=1;j<=N;j++)
{
scanf("%d",&dis[i][j]);
}
}
}
void solve()
{
int i,j,k;
bool A;
for (i=1;i<=N;i++)
{
for (j=i+1;j<=N;j++)
{
A=true;
for (k=1;k<=N;k++)
{
if (k!=i && k!=j)
{
if (dis[i][k]+dis[k][j]==dis[i][j])
{
A=false;
break;
}
}
}
if (A)
{
printf("%d %dn",i,j);
}
}
}
}
int main()
{
init();
solve();
return 0;
}
公路网
一张磁盘被写入了一张公路网。这张磁盘包括一个写有任何两个村庄之间最短路径长的表格。所有的路都是双向的。地图上的村庄所处的位置有以下一个有趣的特点:如果村庄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<c)或(a=c且b<d)对(a,b)在(c,d)之前。
输入样例:
3
0 1 2
1 0 3
2 3 0
输出样例:
1 2
1 3
上次修改时间 2017-02-03