Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.2 kB
2
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define INF 100000000000
using namespace std;

int n, m, k;
int s[17];
int danhSachKe[1005][1005];
long long disDanhSachKe[1005][1005];
long long disMinDanhSachKe[1005][1005];
long long key[1005];
bool vistiedKey[1005];
bool visited[1005];
long long result;

void dkstra(int u){
	for(int i = 0; i <= n; ++i){
		key[i] = INF;
		vistiedKey[i] = false;
	}
	key[u] = 0;
	int k = 0;
	while (k < n)
	{
		long long min = INF;
		int indx = 1;
		for(int i = 1; i <= n; ++i){
			if(min > key[i] && vistiedKey[i] == false){
				min = key[i];
				indx = i;
			}
		}
		vistiedKey[indx] = true;
		for(int i = 1; i <= danhSachKe[indx][0]; ++i){
			if(vistiedKey[danhSachKe[indx][i]] == false
				&& key[indx] + disDanhSachKe[indx][i] < key[danhSachKe[indx][i]]){
					key[danhSachKe[indx][i]] = key[indx] + disDanhSachKe[indx][i];
			}
		}
		k++;
	}
}


void backtrack(int u, int V, long long sum){
	if(sum >= result){
		return;
	}
	if(u == k){
		if(sum + disMinDanhSachKe[V][1] < result){
			result = sum+ disMinDanhSachKe[V][1];
		}
		return;
	} 
	for(int i = 1; i <= k; ++i){
		if(visited[s[i]] == false){
			visited[s[i]] = true;
			backtrack(u+1, s[i],sum + disMinDanhSachKe[V][s[i]]);
			visited[s[i]] = false;
			//
		}
	}
}

int main(){
	//freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; ++tc){
		cin >> n >> m >> k;
		for(int i = 1; i <= n; ++i){
			danhSachKe[i][0] = 0;
		}
		visited[0] = false;
		for(int i = 1; i <= k; i++){
			cin >> s[i];
			visited[s[i]] = false;
		}
		s[0] = 1;
		for(int i = 1; i <= m; ++i){
			int u, v;
			long long w ;
			cin >> u >> v >> w;
			danhSachKe[u][0]++;
			danhSachKe[u][danhSachKe[u][0]] = v;
			disDanhSachKe[u][danhSachKe[u][0]] = w; 
		}
		result = INF;
		for(int i = 0; i <= k; ++i){
			dkstra(s[i]);
			for(int j = 0; j <=k; ++j){
				disMinDanhSachKe[s[i]][s[j]] =  key[s[j]];
			}
		}
		backtrack(0, 1,0);
		if(result != INF){
			cout <<"Case #" << tc << "\n"<< result << endl << endl;
		}
		else{
			cout <<"Case #" << tc << "\n"<< -1 << endl << endl;
		}
	}

	return 0;
}