Untitled

<dd><p class="MsoNormal" align="center" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����; text-align: center;"><b>Tuần trăng mật<o:p></o:p></b></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">Đám cưới anh Uranus diễn ra rất vui vẻ, chỉ có Tomoky là có chút hậm hực. Sau đám cưới, anh Uranus muốn đi tuần trăng mật ở thành phố Đà Lạt xinh đẹp.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">Thành phố Đà Lạt gồm n điểm du lịch trọng điểm, được đánh số từ 1 tới n. Hệ thống giao thông trong vùng gồm m (m &lt;= n*(n-1)) tuyến đường một chiều khác nhau, tuyến đường thứ j (j = 1,2,…m) cho phép đi từ địa điểm u_j tới địa điểm v_j với chi phí đi lại là số nguyên dương c(u_j, v_j).<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">Anh Uranus muốn xuất phát từ điểm du lịch 1 và đi thăm k địa điểm du lịch s_1, s_2, …, s_k (khác địa điểm 1) và sau đó quay về địa điểm xuất phát 1 với tổng chi phí là nhỏ nhất.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">Cho thông tin về hệ thống giao thông và k địa điểm du lịch s_1, s_2, …, s_k. Hãy giúp anh Uranus xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch 1 và đi thăm k địa điểm s_1, s_2, …, s_k sau đó quay về địa điểm du lịch 1 với tổng chi phí nhỏ nhất.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><b>Input<o:p></o:p></b></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">• Dòng đầu tiên chứa số nguyên dương T là số bộ test. Mỗi bộ test gồm:<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">• Dòng thứ nhất chứa 3 số nguyên n, m, k (n &lt;= 1000 và k &lt;= 15).<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">• Dòng thứ hai chứa k số nguyên dương s_1, s_2, …, s_k.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">• Dòng thứ j trong m dòng tiếp theo chứa 3 số nguyên dương u_j, v_j, c(u_j, v_j) cho biết thông tiên về tuyến đường thứ j. Biết rằng u_j luôn khác v_j, và c(u_j, v_j) &lt;= 10^9.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><b>Output<o:p></o:p></b></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">In ra một số nguyên là tổng chi phí nhỏ nhất tìm được. Nếu không tìm được một hành trình du lịch nào, in ra số -1.<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><b>Example<o:p></o:p></b></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><b>Input:<o:p></o:p></b></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">1<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">6 8 2<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">2 5<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">1 2 4<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">2 4 2<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">4 3 3<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">3 1 4<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">4 1 5<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">3 5 5<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">5 3 1<o:p></o:p></span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><span times="" new="" roman",serif"="">5 6 7</span></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;">&nbsp;Output:</p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;">Case #1</p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;">19</p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;"><br></p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;">Case #2</p><p class="MsoNormal" style="color: rgb(0, 0, 0); font-family: " ��=", dotum, ����;">57</p></dd>
package Buoi27.Tuan_trang_mat;

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

public class Solution {

	static int nTourism;
	static int mLine;
	static int kAddress;

	static int[] address;
	static int[][] list;
	static int[] info;
	static long[][] expense = new long[1005][1005];
	static long[][] matrix = new long[1005][1005];

	static int[] queue = new int[1000 * 1000 * 2];
	static int head;
	static int tail;

	static long[] visited;
	static int[] visited_BT;
	static int[] choose;

	static long min;
	static boolean flag;

	public static void enQueue(int value) {
		tail++;
		queue[tail] = value;
	}

	public static int deQueue() {
		head++;
		return queue[head];
	}

	public static void input(Scanner sc) {
		nTourism = sc.nextInt();
		mLine = sc.nextInt();
		kAddress = sc.nextInt() + 1;
		address = new int[kAddress];
		address[0] = 0;
		for (int i = 1; i < kAddress; i++) {
			address[i] = sc.nextInt() - 1;
		}
		list = new int[nTourism][mLine];
		info = new int[nTourism];
		for (int i = 0; i < mLine; i++) {
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			expense[a][b] = sc.nextLong();
			list[a][info[a]] = b;
			info[a]++;
		}
	}

	public static void BFS(int x) {
		head = tail = -1;
		visited = new long[nTourism];
		visited[x] = 1;
		enQueue(x);
		int temp;
		while (head != tail) {
			temp = deQueue();
			for (int i = 0; i < info[temp]; i++) {
				int a = list[temp][i];
				if (visited[a] == 0
						|| visited[a] > visited[temp] + expense[temp][a]) {
					visited[a] = visited[temp] + expense[temp][a];
					matrix[x][a] = visited[temp] + expense[temp][a] - 1;
					enQueue(a);
				}
			}
		}
		for (int i = 0; i < kAddress; i++) {
			if (matrix[x][address[i]] == 0 && x != address[i]) {
				flag = false;
				return;
			}
		}
	}

	public static void backtrack(int k, long sum) {
		if(sum>=min){
			return;
		}
		if (k == kAddress) {
			sum += matrix[choose[k-1]][0];
			if (min > sum) {
				min = sum;
			}
			return;
		}

		for (int i = 1; i < kAddress; i++) {
			if (visited_BT[i] == 0) {
				choose[k] = address[i];
				visited_BT[i] = 1;
				backtrack(k + 1, sum + matrix[choose[k - 1]][choose[k]]);
				choose[k] = 0;
				visited_BT[i] = 0;
			}
		}
	}

	public static void solve() {
		for (int i = 0; i < kAddress; i++) {
			flag = true;
			BFS(address[i]);
			if (!flag) {
				System.out.println(-1);
				return;
			}
		}
		min = Long.MAX_VALUE;
		visited_BT = new int[kAddress];
		visited_BT[0] = 1;
		choose = new int[kAddress];
		choose[0] = 0;
		backtrack(1, 0);
		System.out.println(min);
	}

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		long start = System.currentTimeMillis();
		System.setIn(new FileInputStream(
				"C:\\Users\\SVMC\\Downloads\\input (1).txt"));
		
//		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			input(sc);
			System.out.println("Case #"+test_case);
			solve();
			System.out.println();
		}
		long end = System.currentTimeMillis();
		System.out.println((double) (end - start) / 1000);
	}

}