Untitled
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; } }