3463395_wa.java

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

import java.util.*;

public class Main {

	private Scanner in;
	private int n, m;
	private double length;
	private double [][] cost;

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

	public void run() {
		in = new Scanner (System.in);
		HashMap <String, Integer> hm = new HashMap <String, Integer> ();

		length = in.nextDouble();
		n = in.nextInt();
		cost = new double [n][n];
		hm.clear();
		for (int i = 0; i < n; i++) {
			hm.put(in.next(), i);
		}
		m = in.nextInt();
		for (int i = 0; i < m; i++) {
			int u = hm.get(in.next());
			int v = hm.get(in.next());
			cost[u][v] = cost[v][u] = in.nextDouble();
		}
		prim();
	}
	
	private void prim() {
		int i, j, k;
		double W, min;
		double [] lowcost = new double [n];
		
		W = 0;
		for (i = 0; i < n; i++) {
			lowcost[i] = cost[0][i];
		}
		for(i = 1; i < n; i++) {
			min = 1000000000;
			k = 0;
			for(j = 0; j < n; j++) {
				if(lowcost[j] != 0 && lowcost[j] < min) {
					min = lowcost[j];
					k = j;
				}
			}
			W += min;
			if (W > length) {
				break;
			}
			lowcost[k] = 0;
			for(j = 0; j < n; j++) {
				if(cost[k][j]!=0&&cost[k][j]<lowcost[j]) {
					lowcost[j] = cost[k][j];
				}
			}
		}
		if (W > length) {
			System.out.println("Not enough cable");
		} else {
			System.out.format("Need %.1f miles of cable\n", W);
		}
	}
}