Untitled

mail@pastecode.io avatar
unknown
plain_text
10 months ago
3.4 kB
3
Indexable
Never
import java.util.Scanner;

public class Solution {
	static int M, sumGun, min, maxGun, sV, eV, guns;
	static int[][] arr = new int[101][101];
	static int[] gun = new int[101];
	static int[] count = new int[101];
	static int[] visit = new int[101];
	static int[] temp = new int[3];
	static pQueue pq = new pQueue(100000);

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int t = 1; t <= T; t++) {
			M = sc.nextInt();
			for (int i = 0; i < gun.length; i++) {
				gun[i] = 0;
				count[i] = 0;
				visit[i] = 0;
				for (int j = 0; j < gun.length; j++) {
					arr[i][j] = 0;
				}
			}

			for (int i = 0; i < M; i++) {
				int v = sc.nextInt();
				gun[v] = sc.nextInt();
				count[v] = sc.nextInt();
				for (int j = 0; j < count[v]; j++) {
					int u = sc.nextInt();

					arr[v][u] = 1;
				}

			}

			for (int v = 0; v < M; v++) {
				sumGun = 0;
				maxGun = 0;
				min = 0;
				pq.reset();
				for (int u = 0; u < M; u++) {
					visit[u] = 0;
					if (arr[v][u] == 1) {
						sumGun += gun[v] + gun[u];
						pq.push(0, u, gun[v] + gun[u]);
					}
				}
				int len = pq.size();
				if (len < 2)
					continue;
				visit[v] = 1;

				while (!pq.empty()) {
					temp = pq.pop();
					sV = temp[0];
					eV = temp[1];
					guns = temp[2];
					if (visit[eV] == 1)
						continue;
					maxGun += guns;
					visit[eV] = 1;
					for (int i = 0; i < M; i++) {
						if (visit[i] == 0 && arr[eV][i] == 1) {
							sumGun += gun[eV] + gun[i];
							pq.push(eV, i, gun[eV] + gun[i]);
						}
					}

				}
				min = sumGun - maxGun;
			}

			System.out.println("Case #" + t);
			System.out.println(min);

		}
		sc.close();
	}

}

class pQueue {
	static int capacity, size, lChild, rChild, parent, child, larger;
	static int[][] arr;
	static int[] tmp, res;

	pQueue(int c) {
		capacity = c;
		size = 0;
		arr = new int[capacity][3];
		tmp = new int[3];
		res = new int[3];
	}

	void push(int x, int y, int z) {
		arr[size][0] = x;
		arr[size][1] = y;
		arr[size][2] = z;
		size++;
		heapUp();
	}

	int[] pop() {
		for (int i = 0; i < 3; i++) {
			res[i] = arr[0][i];
			arr[0][i] = arr[size - 1][i];
		}

		size--;

		heapDown();

		return res;
	}

	private void heapDown() {
		// TODO Auto-generated method stub
		parent = 0;
		while (true) {
			lChild = parent * 2 + 1;
			rChild = parent * 2 + 2;
			larger = lChild;

			if (rChild < size && arr[rChild][2] > arr[larger][2]) {
				larger = rChild;
			}
			if (larger < size && arr[larger][2] > arr[parent][2]) {
				swap(larger, parent);
				parent = larger;
			} else {
				break;
			}

		}

	}

	private void heapUp() {
		// TODO Auto-generated method stub
		child = size - 1;

		while (child != 0) {
			int parent = (child - 1) / 2;
			if (arr[child][2] > arr[parent][2]) {
				swap(child, parent);
				child = parent;
			} else {
				break;
			}
		}
	}

	private void swap(int c, int p) {
		// TODO Auto-generated method stub
		for (int i = 0; i < 3; i++) {
			tmp[i] = arr[c][i];
			arr[c][i] = arr[p][i];
			arr[p][i] = tmp[i];
		}
	}

	boolean empty() {
		return size == 0;
	}

	int size() {
		return size;
	}

	int[] valueOf(int idx) {
		return arr[idx];
	}

	void reset() {
		size = 0;
	}

}