Internet服务供应商想知道从站点A传送数据到站点B哪谢公司提供了必要的连接(就是在链路中都出现过的公司)。
思路:f[i][j]的值表示从结点i到j经过了那些必要的公司,由于最多只有26个公司,故可将状态进行压缩
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
using namespace std;
const int N=205;
int n,f[N][N];
char s[N];
void floyd() {
for (int k=1; k<=n; k++)
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) {
f[i][j]|=f[i][k]&f[k][j];
}
}
int main() {
while (scanf("%d",&n), n) {
int u,v;
memset(f,0,sizeof f);
while (scanf("%d%d",&u,&v), u) {
scanf("%s",s);
for (int i=0; i<strlen(s); i++)
f[u][v]|=(1<<(s[i]-'a'));
}
floyd();
while (scanf("%d%d",&u,&v), u) {
int st=f[u][v], c=0; //c表示st的第几位
while (st) {
if (st&1) putchar(c+'a');
st>>=1, c++;
}
if (c==0) putchar('-');
putchar('
');
}
putchar('
');
}
return 0;
}