枚举起点和公司，每次用DFS跑一遍图，预处理出所有的答案。询问的时候很快就能得到答案。
#include<cstdio> #include<cmath> #include<cstring> #include<vector> #include<algorithm> using namespace std; int jz[300][300][30]; int ans[300][300][30]; int flag[300]; vector<int>ljb[300]; int n; int S,T,G; void DFS(int now) { ans[S][now][G]=1; int i; for(i=0; i<ljb[now].size(); i++) { if(jz[now][ljb[now][i]][G]==1&&flag[ljb[now][i]]==0) { flag[ljb[now][i]]=1; DFS(ljb[now][i]); } } } int main() { int i,j,k; while(~scanf("%d",&n)) { if(n==0) break; for(i=0; i<=n; i++) ljb[i].clear(); memset(jz,0,sizeof(jz)); memset(ans,0,sizeof(ans)); while(1) { int u,v; char s[1000]; scanf("%d%d",&u,&v); if(u==0&&v==0) break; scanf("%s",s); ljb[u].push_back(v); for(i=0; s[i]; i++) jz[u][v][s[i]-'a']=1; } for(i=1; i<=n; i++) { for(j=0; j<26; j++) { memset(flag,0,sizeof(flag)); S=i; G=j; DFS(S); } } while(1) { int u,v; scanf("%d%d",&u,&v); if(u==0&&v==0) break; int i; int sc=0; for(i=0; i<26; i++) { if(ans[u][v][i]==1) { sc=1; printf("%c",i+'a'); } } if(sc==0) printf("-"); printf(" "); } printf(" "); } return 0; }