Untitled

 avatar
unknown
plain_text
2 years ago
2.2 kB
8
Indexable
#include <iostream>
using namespace std;
#define INF 100000000000

int n,m,k;
int place[16];
int c_n[1001];
long long adjArr[1001][1001];
long long disData[1001][1001];
long long key[1001];
int visit[1001];
long long distanceArr[1001][1001];
int visitPlace[16];
long long kq;
int findMinKey(){
	long long minKey = INF;
	int minIndex = 0;
	for(int i = 1; i<= n; i ++){
		if(key[i] < minKey && visit[i] == 0) minKey = key[i], minIndex = i;
	}
	return minIndex;
}
bool checkPassed(){
	for(int i = 1; i <= k; i++){
		if(visitPlace[i] == 0) return false;
	}
	return true;
}
void minDis(int x){
	for(int i = 1; i <= n; i++){
		key[i] = INF;
		visit[i] = 0;
	}
	key[x] = 0;
	int i = 1;
	while(i <= n){
		int a = findMinKey();
		visit[a] = 1;
		for(int j = 1; j <=c_n[a]; j++){
			if(disData[j][a] > 0 && visit[adjArr[j][a]] == 0 && disData[j][a] + key[a] < key[adjArr[j][a]]){
				key[adjArr[j][a]] = disData[j][a] + key[a];
			}
		}
	i++;
	}
}
void backtrack(int v,long long d, int l){
	if(d >= kq) return;
	if(l == k){
			if(d + distanceArr[place[v]][1] < kq) kq = d + distanceArr[place[v]][1];
		return;
	}
	for(int i = 1; i <= k; i++){
		if(visitPlace[i] == 0){
			visitPlace[i]++;
			backtrack(i,d+distanceArr[place[v]][place[i]], l + 1);
			visitPlace[i]--;
		}
	}
}
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 <= k; i++){
			cin >> place[i];
		}
		place[0] = 1;
		for(int i = 1; i <= n; i++){
			c_n[i] = 0;
			for(int j = 1; j <= n; j++){
				adjArr[i][j] = 0;
			}
		}
		for(int i = 0; i < m; i++){
			int x,y,dis;
			cin >> x >> y >> dis;
			c_n[x]++;
			adjArr[c_n[x]][x] = y;
			disData[c_n[x]][x] = dis;
		}
		for(int i = 0; i <= k; i++){
			minDis(place[i]);
			for(int j = 0; j <=k; j++){
				distanceArr[place[i]][place[j]] = key[place[j]];
			}
		}
		kq = INF;
		for(int i = 1; i <= k; i++){
			visitPlace[i] = 0;
		}
		visitPlace[0] = 1;
		backtrack(0,0,0);
		cout << "Case #" << tc << endl;
		if(kq == INF) cout << - 1 << endl << endl;
		else cout << kq << endl << endl;
	}
	return 0;
}
Editor is loading...