思路:floyd + 位运算。map[i][j]的二进制位前26位表示i到j路径里面字母a-z的存在情况,为1说明该字母存在,为0不存在。
#include<iostream> #include<cstdio> #include<cstring> #include<string> #define MAX 205 using namespace std; string str; int map[MAX][MAX]; void Switch(int n, int m){ for(int i = 0;i < str.size();i ++){ map[n][m] |= 1 << (str.at(i) - 'a'); } } int main(){ int n, u, v; /* freopen("in.c", "r", stdin); */ while(~scanf("%d", &n) && n){ memset(map, 0, sizeof(map)); while(cin >> u >> v && u && v){ str.clear(); cin >> str; Switch(u, v); } for(int k = 1;k <= n;k ++) for(int i = 1;i <= n;i ++) for(int j = 1;j <= n;j ++) map[i][j] |= (map[i][k] & map[k][j]); while(cin >> u >> v && u && v){ int flag = 0, temp = map[u][v]; for(int i = 0;i < 26;i ++){ if(temp & 1){ flag = 1; char c = i + 'a'; cout << c; } temp >>= 1; } if(!flag) cout << "-"; cout << endl; } cout << endl; } return 0; }