Fiber Network
Several startup companies have decided to build a better Internet, called the "FiberNet". They have already installed many nodes that act as routers all around the world. Unfortunately, they started to quarrel about the connecting lines, and ended up with every company laying its own set of cables between some of the nodes. 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
The input contains several test cases. Each test case starts with the number of nodes of the network n. Input is terminated by n=0. Otherwise, 1<=n<=200. Nodes have the numbers 1, ..., n. Then follows a list of connections. Every connection starts with two numbers A, B. The list of connections is terminated by A=B=0. Otherwise, 1<=A,B<=n, and they denote the start and the endpoint of the unidirectional connection, respectively. For every connection, the two nodes are followed by the companies that have a connection from node A to node B. A company is identified by a lower-case letter. The set of companies having a connection is just a word composed of lower-case letters.
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
For each query in every test case generate a line containing the identifiers of all the companies, that can route data packages on their own connections from the start node to the end node of the query. If there are no companies, output "-" instead. Output a blank line after each test case.
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-
Source
题目类型：全源最短路思想(Floyd)
算法分析：使用Floyd算法的迭代思想，矩阵ans[i][j]中存放的是节点i到节点j中存在的公司集合(字符串)。使用位运算的相关技巧，用从低到高的26个二进制位表示两点之间存在的公司(1位)的情况。对于每一次迭代，使用ans[i][j] = 集合或运算(ans[i][j], ans[i][k] 集合与运算ans[k][j])。然后对于每个查询直接输出结果即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 |
#include <iostream> #include <fstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int maxn = 666 + 66; int ans[maxn][maxn]; int n; void floyd () { int i, j, k; for (k = 1; k <= n; k++) { for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { ans[i][j] |= (ans[i][k] & ans[k][j]); } } } } int main() { // ifstream cin ("aaa.txt"); while (cin >> n) { if (n == 0) break; int i; int val_a, val_b; char input[36]; memset (ans, 0, sizeof (ans)); while (cin >> val_a >> val_b) { if (val_a == 0 && val_b == 0) break; cin >> input; int j; for (j = 0; input[j]; j++) ans[val_a][val_b] |= 1 << (input[j] - 'a'); } floyd (); while (cin >> val_a >> val_b) { if (val_a == 0 && val_b == 0) break; for (i = 0; i < 26; i++) { if (ans[val_a][val_b] & (1 << i)) cout << (char) (i + 'a'); } if (!ans[val_a][val_b]) cout << "-" << endl; else cout << endl; } cout << endl; } return 0; } |
- « 上一篇：poj2559
- poj2576：下一篇 »