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