POJ 2570 - Fiber Network

http://poj.org/problem?id=2570

概要

\(n\) 個のノードからなる有向グラフが与えられる。 各エッジには小文字のアルファベットからなる文字列のラベルがついており、その文字列に含まれるアルファベットで表される会社の回線が存在することを表している。

その後2つのノード \(A, B\) からなるクエリがいくつか与えられ、\(A\) から \(B\) への回線を持っている会社のアルファベットをすべて答える。

制約

解法

ワーシャルフロイド。 会社の種類は26しかないので、ビットでもって計算する。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   while (scanf("%d", &N) != EOF && N != 0) {
 9     static int dist[200][200];
10     for (int i = 0; i < N; i++) {
11       fill_n(dist[i], N, 0);
12     }
13     for (int u, v; scanf("%d %d", &u, &v) != EOF && u != 0;) {
14       --u;  --v;
15       char buf[32];
16       scanf("%s", buf);
17       for (int i = 0; buf[i]; i++) {
18         dist[u][v] |= 1 << (buf[i] - 'a');
19       }
20     }
21 
22     for (int k = 0; k < N; k++) {
23       for (int i = 0; i < N; i++) {
24         for (int j = 0; j < N; j++) {
25           dist[i][j] |= dist[i][k] & dist[k][j];
26         }
27       }
28     }
29 
30     for (int u, v; scanf("%d %d", &u, &v) != EOF && u != 0;) {
31       --u;  --v;
32       bool found = false;
33       for (int i = 0; i < 26; i++) {
34         if (dist[u][v] & (1<<i)) {
35           found = true;
36           putchar(i+'a');
37         }
38       }
39       if (!found) {
40         putchar('-');
41       }
42       putchar('\n');
43     }
44     putchar('\n');
45   }
46   return 0;
47 }
poj/2570.cc