POJ 2570 Fiber Network（最短路 二進制處理）

POJ 2570 Fiber Network（最短路 二進制處理）

題目翻譯

一些公司決定搭建一個更快的網絡，稱為“光纖網”。他們已經在全世界建立了許多站點，這 些站點的作用類似於路由器。不幸的是，這些公司在關於站點之間的接線問題上存在爭論，這樣“光纖網”項目就被迫終止了，留下的是每個公司自己在某些站點之間鋪設的線路。 現在，Internet 服務供應商，當想從站點 A傳送數據到站點 B，就感到困惑了，到底哪個公司 能夠提供必要的連接。請幫助供應商回答他們的查詢，查詢所有可以提供從站點 A到站定 B的線 路連接的公司。

輸入描述：

輸入文件包含多個測試數據。每個測試數據第 1行為一個整數 n，代表網絡中站點的個數，n = 0 代表輸入結束，否則 n的范圍為：1≤n≤200。站點的編號為 1, …, n。接下來列出了這些站 點之間的連接。每對連接占一行，首先是兩個整數 A和B，A = B = 0 代表連接列表結束，否則 A、 B的范圍為：1≤A, B≤n，表示站點 A和站點 B之間的單向連接；每行後面列出了擁有站點 A到 B之間連接的公司，公司用小寫字母標識，多個公司的集合為包含小寫字母的字符串。 連接列表之後，是供應商查詢的列表。每個查詢包含兩個整數 A和B，A = B = 0 代表查詢列 表結束，也代表整個測試數據結束，否則 A、B 的范圍為：1≤A, B≤n，代表查詢的起始和終止 站點。假定任何一對連接和查詢的兩個站點都不相同。

輸出描述：

對測試數據中的每個查詢，輸出一行，為滿足以下條件的所有公司的標識：這些公司可以通 過自己的線路為供應商提供從查詢的起始站點到終止站點的數據通路。如果沒有滿足條件的公司， 則僅輸出字符"-"。每個測試數據的輸出之後輸出一個空行。

公司最多有26個 可以用2進制來表示站點間的連接關系 如果提供站點 1 到站點 2 的連接的公司集合為{ 'a', 'b', 'c' }，可以用 “00000000000000000000000000000111”表示，提供站點 2到站點 3的連接的公司集合為{ 'a', 'd' }，用“00000000000000000000000000001001”表示，這兩個整數進行二進制與運算後 得到“00000000000000000000000000000001”，表示通過中間站點 2，提供站點 1到站點 3的連 接的公司集合為{ 'a' }。

這樣就floyd進行處理就類似最短路問題了

#include
#include
using namespace std;
const int N = 205;
int d[N][N], n;

void floyd()
{
    for(int k = 1; k <= n; ++k)
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
        d[i][j] |= (d[i][k] & d[k][j]);

}

int main()
{
    int a, b;
    char s[30];
    while(scanf("%d", &n), n)
    {
        memset(d, 0, sizeof(d));
        while(scanf("%d%d", &a, &b), a)
        {
            scanf("%s", s);
            for(int i = 0; s[i] != '\0'; ++i)
                d[a][b] = d[a][b] | (1 << s[i] - 'a');
        }
        floyd();
        while(scanf("%d%d", &a, &b), a)
        {
            for(char c = 'a'; c <= 'z'; ++c)
                if(d[a][b] & (1 << c - 'a')) printf("%c", c);
            if(d[a][b] == 0) printf("-");
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

Fiber Network

Description

Several startup companies have decided to build a better Internet, called the "FiberNet". They have already installed many nodes that act as routers all around the world. Unfortunately, they started to quarrel about the connecting lines, and ended up with every company laying its own set of cables between some of the nodes.
Now, service providers, who want to send data from node A to node B are curious, which company is able to provide the necessary connections. Help the providers by answering their queries.

Input

The input contains several test cases. Each test case starts with the number of nodes of the network n. Input is terminated by n=0. Otherwise, 1<=n<=200. Nodes have the numbers 1, ..., n. Then follows a list of connections. Every connection starts with two numbers A, B. The list of connections is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the unidirectional connection, respectively. For every connection, the two nodes are followed by the companies that have a connection from node A to node B. A company is identified by a lower-case letter. The set of companies having a connection is just a word composed of lower-case letters.
After the list of connections, each test case is completed by a list of queries. Each query consists of two numbers A, B. The list (and with it the test case) is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the query. You may assume that no connection and no query contains identical start and end nodes.

Output

For each query in every test case generate a line containing the identifiers of all the companies, that can route data packages on their own connections from the start node to the end node of the query. If there are no companies, output "-" instead. Output a blank line after each test case.

Sample Input

3
1 2 abc
2 3 ad
1 3 b
3 1 de
0 0
1 3
2 1
3 2
0 0
2
1 2 z
0 0
1 2
2 1
0 0
0

Sample Output

ab
d
-

z
-