3535458_ac_2172ms_5532k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main {
	private Scanner in;
	private int n;
	private int [][] con = new int [200][200];

	public static void main(String [] args) {
		new Main().run();
	}

	private void floyd() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (con[j][i] != 0) {
					for (int k = 0; k < n; k++) {
						con[j][k] |= (con[j][i] & con[i][k]);
					}
				}
			}
		}
	}

	private void run() {
		in = new Scanner (System.in);
		int u, v;

		while (true) {
			n = in.nextInt();
			if (n == 0) {
				break;
			}
			for (int i = 0; i < n; i++) {
				Arrays.fill(con[i], 0);
			}
			while (true) {
				u = in.nextInt() - 1;
				v = in.nextInt() - 1;
				if (u == -1 && v == -1) {
					break;
				}
				con[u][v] = getInteger(in.next());
			}
			floyd();
			while (true) {
				u = in.nextInt() - 1;
				v = in.nextInt() - 1;
				if (u == -1 && v == -1) {
					break;
				}
				int t = con[u][v];
				if (t == 0) {
					System.out.println("-");
					continue;
				}
				char ch = 'a';
				while (t != 0) {
					if (t % 2 == 1) {
						System.out.print(ch);
					}
					ch++;
					t = t >> 1;
				}
				System.out.println();
			}
			System.out.println();
		}
	}

	private int getInteger(String str) {
		int ret = 0;

		for (int i = 0; i < str.length(); i++) {
			int t = str.charAt(i) - 'a';
			ret |= (1 << t);
		}
		return ret;
	}
}