学步园

思路：因为只有26个字母 所以可能用二进制去表示每个公司 1表示该路径上有该公司 比如说 1-->3
这条路径上有 abc这三个公司 则mat[1][3]  二进制表示为00..0111;
然后就是用floyd传递闭包。

//408K   
63MS
#include <stdio.h>
#include <string.h>
#define M 250

int mat[M][M];

void print(int num)
{
    char
s[30];
    int k =
0,count = 0;
    while
(num)
    {
       
if (num&1)
           
s[k++] = 'a' + count;
       
count ++;
       
num = num>>1;
    }
    s[k] =
'\0';
    printf
("%s\n",s);
}
int main ()
{
    char
str[30];
    int
n,u,v;
    while (scanf
("%d",&n)&&n)
    {
       
memset (mat,0,sizeof(mat));
       
while (scanf ("%d%d",&u,&v))
       
{
           
if (u == 0 && v == 0)
               
break;
           
scanf ("%s",str);
           
for (int i = 0;str[i]!= '\0';i
++)       
//转换成二进制表示
               
mat[u][v] =
mat[u][v]|(1<<(str[i]-'a'));
       
}
 
       
for (int k = 1;k <= n;k
++)               
//floyd
           
for (int i = 1;i <= n;i ++)
               
for (int j = 1;j <= n;j ++)
                   
if (mat[i][k]&mat[k][j])