# Untitled

unknown
plain_text
a year ago
3.5 kB
2
Indexable
Never
```package tuan_trang_mat;

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

public class Solution {
static int n, m, k, check;
static long res;
static int[][] a;
static int[] vitri, visit, comb, visithv, parent;
static long[][] kc;

static void cal_distan() {
kc = new long[n + 1][n + 1];

for (int i = 0; i <= k; i++) {
int[] q = new int[10000];
long[][] lan = new long[n + 1][n + 1];
int front = 0, rear = 1;
q[front] = vitri[i];
visit = new int[n + 1];
visit[vitri[i]] = 1;
parent = new int[n+1];
while (front < rear) {
int x = q[front];
visit[x] = 2;
for (int j = 1; j <= n; j++) {
if (a[x][j] > 0 && visit[j] == 0) {
q[rear] = j;
rear++;
lan[vitri[i]][j] = lan[vitri[i]][x] +  a[x][j];
visit[j] = 1;
}else
if (a[x][j] > 0 && visit[j] == 1 && lan[vitri[i]][j] > lan[vitri[i]][x] +  a[x][j]) {
lan[vitri[i]][j] = lan[vitri[i]][x] +  a[x][j];

}else
if (a[x][j] > 0 && visit[j] == 2 && lan[vitri[i]][j] > lan[vitri[i]][x] +  a[x][j]) {
q[rear] = j;
rear++;
lan[vitri[i]][j] = lan[vitri[i]][x] +  a[x][j];
}
}
front++;
}
for (int j = 1; j <= n; j++) {
kc[vitri[i]][j] = lan[vitri[i]][j];
}
}
}

static void backtrack(int count, long chiphi){
if(count == k +1 ){

//			for(int i = 0; i <=k ; i++){
//				System.out.print(comb[i] + " ");
//			}
//			System.out.println();
long x = chiphi + kc[comb[count-1]][1];
//			System.out.println("k " + count + " " + kc[comb[count-1]][1]);
//			for(int i = 1; i <= k;i++)
if(x < res) {
//				check =1;
res = x;
}
return;
}
if(chiphi >= res){
return;
}

for(int i = 1; i <= k ; i++){
if(visithv[i] == 0){
visithv[i] = 1;
comb[count] = vitri[i];
if(kc[comb[count-1]][comb[count]] == 0){
check = 0;
return;
}
//				System.out.println((count +1) + " kc " + kc[comb[count-1]][comb[count]]);
backtrack(count +1 , chiphi + kc[comb[count-1]][comb[count]]);
visithv[i] = 0;
}
}
}

public static void main(String[] args) {

try {
System.setIn(new FileInputStream("input(ttm).txt"));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
Scanner scanner = new Scanner(System.in);
int test = scanner.nextInt();
for (int t = 1; t <= test; t++) {
n = scanner.nextInt();
m = scanner.nextInt();
k = scanner.nextInt();
vitri = new int[k+1];
vitri[0] = 1;
for (int i = 1; i <= k; i++) {
vitri[i] = scanner.nextInt();
}
a = new int[n + 1][n + 1];
for (int i = 0; i < m; i++) {
a[scanner.nextInt()][scanner.nextInt()] = scanner.nextInt();
}

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

check = 1;
res = Long.MAX_VALUE;

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

visithv = new int[k+1];
comb = new int[k+1];
comb[0] = 1;

backtrack(1, 0);
if(check == 0){
System.out.println("Case #" + t + "\n-1\n" );
}else{
System.out.println("Case #" + t + "\n" + res+"\n");
}
}
scanner.close();
}
}
```