Fiber Network Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2725 Accepted: 1252 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 -這也是一道典型的floyd。這個題有意思的地方在於對於輸入數據的處理，這個是關鍵，其他的其實非常簡單，筆者比較愚蠢，這個處理搞了半天才搞懂。下面是代碼：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int m[201][201];//floyd中的矩陣
int n;
int i,j,k;//循環變量
void floyd(){//模板
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
m[i][j]=m[i][j]|(m[i][k]&m[k][j]);//這裡是這道題目的關鍵，這裡要求不是最短的路徑，而且是要求有哪些點可以滿足條件，所以要進行變式
}
}
int main(){
int A,B;
char str[100];
char ch;
while(scanf("%d",&n) && n){
memset(m,0,sizeof(m));
while(scanf("%d%d",&A,&B)){
if(A==0&&B==0)
break;
scanf("%s",str);
for(i=0;str[i];++i)
m[A][B]=m[A][B]|(1<<(str[i]-'a'));//這是我在這道題裡面學習到的數據處理技巧，通過先將輸入的數據轉換成二進制，然後在矩陣中的元素按位求或，記住是|而不是||，筆者就是跪在這兒了一個小時
}
floyd();
while(scanf("%d%d",&A,&B)){
if(A==0&&B==0)
break;
for(ch='a';ch<='z';++ch)
{
if(m[A][B]&(1<<ch-'a'))
putchar(ch);
}
if(!m[A][B])
putchar('-');
printf("\n");
}
printf("\n");
}
return 0;
}
