Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
3.9 kB
2
Indexable
Never

import java.io.FileInputStream;
import java.util.Scanner;
import java.util.Stack;

public class TanCongThanhTri {
    public static void main(String args[]) throws Exception
    {
		/*
		   The method below means that the program will read from input.txt, instead of standard(keyboard) input.
		   To test your program, you may save input data in input.txt file,
		   and call below method to read from the file when using nextInt() method.
		   You may remove the comment symbols(//) in the below statement and use it.
		   But before submission, you must remove the freopen function or rewrite comment symbols(//).
		 */
        System.setIn(new FileInputStream("src/samsung_srv_training/dfs/input.txt"));

		/*
		   Make new scanner from standard input System.in, and read data.
		 */
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
		/*
   			Read each test case from standard input.
   		*/

//		long begin = System.currentTimeMillis();
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int n = sc.nextInt();
            int[] soMayBanDa = new int[n];
            int[][] mat = new int[n][n];
            for (int i =0; i <n; ++i) {
                sc.nextInt();
                soMayBanDa[i] = sc.nextInt();
                int k = sc.nextInt();
                for (int j = 1; j <= k; ++j) {
                    int y = sc.nextInt();
                    mat[i][y] = 1;
                }
            }

            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (mat[i][j] == 1) {
                        mat[i][j] = soMayBanDa[i] + soMayBanDa[j];
                    }
                }
            }

//            for (int i = 0; i < n; ++i) {
//                for (int j = 0; j < n; ++j) {
//                    System.out.print(mat[i][j] + " ");
//                }
//                System.out.println();
//            }

            int res = 0;
            int cnt = 0;
            Stack stack = new Stack();
            int[] parent;
            boolean[] visited;
            int[] visitTime;
                int min = Integer.MAX_VALUE;
                stack.removeAllElements();
                parent = new int[n];
                visitTime = new int[n];
                visited = new boolean[n];

                int dfsTime = 0;
                stack.push(0);
                parent[0] = -1;
                visited[0] = true;
                visitTime[0] = dfsTime;
                while (!stack.empty()) {
                    int temp = (int) stack.pop();
                    for (int j = 0; j < n; ++j) {
                        if (j == temp || j == parent[temp]) continue;
                        else {
                            if (!visited[j]) {
                                if (mat[temp][j] != 0) {
                                    stack.push(j);
                                    visited[j] = true;
                                    visitTime[j] = ++dfsTime;
                                    parent[j] = temp;
                                    if (mat[temp][j] < min) {
                                        min = mat[temp][j];
                                    }
                                }
                            } else {
                                if (j != parent[temp] && visitTime[j] < visitTime[temp] && mat[temp][j] != 0) {
                                    res += min;
                                    cnt++;
                                }
                            }
                        }
                    }
                }
            System.out.println(res);
        }
//		System.out.println(System.currentTimeMillis()-begin);
    }
}
Leave a Comment