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<cstdio>
#include<cstring>
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;
}

Description

Input

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
-