POJ --2570 Fiber Network
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 2896 | Accepted: 1335 |
Description
Now, service providers, who want to send data from node A to node B are curious, which company is able to provide the necessary connections. Help the providers by answering their queries.
Input
After the list of connections, each test case is completed by a list of queries. Each query consists of two numbers A, B. The list (and with it the test case) is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the query. You may assume that no connection and no query contains identical start and end nodes.
Output
Sample Input
3 1 2 abc 2 3 ad 1 3 b 3 1 de 0 0 1 3 2 1 3 2 0 0 2 1 2 z 0 0 1 2 2 1 0 0 0
Sample Output
ab d - z -
思路:floyd + 位运算。map[i][j]的二进制位前26位表示i到j路径里面字母a-z的存在情况,为1说明该字母存在,为0不存在。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #define MAX 205 6 using namespace std; 7 string str; 8 int map[MAX][MAX]; 9 void Switch(int n, int m){ 10 for(int i = 0;i < str.size();i ++){ 11 map[n][m] |= 1 << (str.at(i) - ‘a‘); 12 } 13 } 14 int main(){ 15 int n, u, v; 16 /* freopen("in.c", "r", stdin); */ 17 while(~scanf("%d", &n) && n){ 18 memset(map, 0, sizeof(map)); 19 while(cin >> u >> v && u && v){ 20 str.clear(); 21 cin >> str; 22 Switch(u, v); 23 } 24 for(int k = 1;k <= n;k ++) 25 for(int i = 1;i <= n;i ++) 26 for(int j = 1;j <= n;j ++) 27 map[i][j] |= (map[i][k] & map[k][j]); 28 while(cin >> u >> v && u && v){ 29 int flag = 0, temp = map[u][v]; 30 for(int i = 0;i < 26;i ++){ 31 if(temp & 1){ 32 flag = 1; 33 char c = i + ‘a‘; 34 cout << c; 35 } 36 temp >>= 1; 37 } 38 if(!flag) 39 cout << "-"; 40 cout << endl; 41 } 42 cout << endl; 43 } 44 return 0; 45 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。