POI 1998 公路網 Road net
本文正體字版由OpenCC轉換
非常簡單的枚舉，三重循環。對於每一個城市對，枚舉中間城市，如果中間有城市，則不是“相鄰城市”，否則就是，輸出即可。
/*
* 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