题目大意是，某条道路由一些公司修建，修建道路的公司可以提供这条路上的连通，询问哪些公司可以提供从A到B的路径。
类似于Floyed的算法。用二进制数表示一个集合。
以下是我的代码：
/*
* Author: lee1r
* Created Time: 2011/8/2 15:57:29
* File Name: poj2570.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(207);
int n,cnt,d[kMaxn][kMaxn];
map<string,int> id;
int main()
{
//freopen("data.in","r",stdin);
while(scanf("%d",&n)==1 && n)
{
cnt=0;
memset(d,0,sizeof(d));
int u,v;
while(scanf("%d%d",&u,&v)==2 && (u || v))
{
string company;
cin>>company;
for(int i=0;i<company.size();i++)
d[u][v]|=(1<<(company[i]-'a'));
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]|=d[i][k]&d[k][j];
while(scanf("%d%d",&u,&v)==2 && (u || v))
{
bool found(false);
for(int i=0;i<26;i++)
if(d[u][v]&(1<<i))
{
printf("%c",(char)(i+'a'));
found=true;
}
if(!found)
printf("-");
printf("\n");
}
printf("\n");
}
return 0;
}
posted on 2011-08-02 16:13
lee1r 阅读(288)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论