Untitled

mail@pastecode.io avatar
unknown
plain_text
10 months ago
1.5 kB
2
Indexable
Never
package Graph;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

class KhongMinh {

	public static int V;
	public static int[][] adj;
	public static int[] count;
	public static int min;

	public static boolean isCyclicUtil(int i, boolean[] visited) {
		if (visited[i]) {
			return true;
		}

		visited[i] = true;
		for (int c = 0; c < V; c++) {
			if (adj[i][c] == 1) {
				if (isCyclicUtil(c, visited))
					if (min > count[i] + count[c]) {
						min = count[i] + count[c];
					}
				return true;
			}
		}
		visited[i] = false;
		return false;
	}

	public static boolean isCyclic() {
		boolean[] visited = new boolean[V];
		min = 9999999;
		for (int i = 0; i < V; i++) {
			if (isCyclicUtil(i, visited))
				return true;
		}
		return false;
	}

	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("Text"));
		Scanner scanner = new Scanner(System.in);
		int tc = scanner.nextInt();
		for (int Case = 1; Case <= tc; Case++) {
			V = scanner.nextInt();
			adj = new int[V][V];
			count = new int[V];
			for (int i = 0; i < V; i++) {
				int index = scanner.nextInt();
				count[index] = scanner.nextInt();
				int gr = scanner.nextInt();
				for (int j = 0; j < gr; j++) {
					int x = scanner.nextInt();
					adj[i][x] = 1;
				}

			}
			System.out.println("Case #" + Case);
			if (isCyclic())
				System.out.println(min);
		}
	}
}