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

相關日誌