最短路变形。
题意是说不同的点之间有不同的公司建立了不同连接。
询问 A,B之间如果存在通路，有那些公司。
我用bool g[][][26] 来表示26个字母。然后Floyd， G++就超时。C++ 就AC了。
然后看别人代码才知道还有位运算……ORZ。。。
自己的代码：C++ AC。813ms
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
bool g[201][201][26];
int n;
void Flyod()
{
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int l=0;l<26;l++)
{
if(g[i][k][l]&&g[k][j][l])
g[i][j][l]=1;
}
}
}
}
}
int main()
{
while(scanf("%d",&n),n)
{
int u,v;
char tmp[26];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
memset(g[i][j],0,sizeof(g[i][j]));
while(scanf("%d%d",&u,&v))
{
if(u==0&&v==0)break;
scanf("%s",tmp);
for(int i=0;tmp[i]!='\0';i++)
{
g[u][v][tmp[i]-'a']=1;
}
}
Flyod();
while(scanf("%d%d",&u,&v))
{
if(u==0&&v==0)break;
bool flag=0;
for(int k=0;k<26;k++)
{
if(g[u][v][k])
{
printf("%c",k+'a');
flag=1;
}
}
if(!flag)
puts("-");
else
puts("");
}
puts("");
}
}
后面写的 位运算的代码：G++ 63ms
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;
int m[201][201];
int n;
int main( )
{
int A, B;
char str[27];
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(int i=0; str[i]; i++ )
{
m[A][B] |= 1 << (str[i] - 'a');
}
}
int i,j,k;
for( k=1; k<=n; k++ )
{
for( i=1; i<=n; i++ )
{
for( j=1; j<=n; j++ )
{
m[i][j] |= m[i][k] & m[k][j];
}
}
}
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( '-' );
puts("");
}
puts("");
}
return 0;
}