3446875_ac_266ms_2216k.java

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

import java.util.*;

public class Main {
	private Scanner in;
	private int m, n, p;
	private int [][] map;
	private HashMap <String, Integer> hm = new HashMap <String, Integer> ();
	private final static int INF = 1000000;

	public static void main(String [] args) {
		System.out.println("SHIPPING ROUTES OUTPUT\n");
		new Main().run();
		System.out.println("END OF OUTPUT");
	}

	private void floyd() {
		for (int k = 0; k < m; k++) {
			for (int i = 0; i < m; i++) {
				if (map[i][k] != INF) {
					for (int j = 0; j < m; j++) {
						int tmp = map[i][k] + map[k][j];
						if (tmp < map[i][j]) {
							map[i][j] = tmp;
						}
					}
				}
			}
		}
	}

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

		cas = in.nextInt();
		while (cas-- > 0) {
			m = in.nextInt();
			n = in.nextInt();
			p = in.nextInt();
			System.out.println("DATA SET " + (now++) + "\n");
			hm.clear();
			map = new int [m][m];
			for (int i = 0; i < m; i++) {
				hm.put(in.next(), i);
				Arrays.fill(map[i], INF);
			}
			for (int i = 0; i < n; i++) {
				u = hm.get(in.next());
				v = hm.get(in.next());
				map[u][v] = map[v][u] = 1;
			}
			floyd();
			for (int i = 0; i < p; i++) {
				w = in.nextInt();
				u = hm.get(in.next());
				v = hm.get(in.next());
				if (map[u][v] == INF) {
					System.out.println("NO SHIPMENT POSSIBLE");
				} else {
					System.out.println("$" + map[u][v] * 100 * w);
				}
			}
			System.out.println();
		}
		in.close();
	}
}