poj 2263&& zoj1952 floyd

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;
}

 

补充：软件开发 , C++ ,