Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
0
Indexable
Never
#include <iostream>

using namespace std;
#define maxn 1001
#define maxm 1000000
#define maxk 16
#define maxd 10000
int n, m, k, ans;
int travel[maxk];
int contact[maxn][maxn];
int dis[maxn][maxn];
int vis[maxn];
void imports(){
	cin >> n >> m >> k;
	for(int i = 0; i < k ; i++){
		cin >> travel[i];
	}
	int f, t;
	for(int i = 0; i < m; i++){
		cin >> f >> t;
		cin >> contact[f][t];
	}
}

void reset(){
	for(int i = 0; i < maxk ; i++){
		travel[i] = 0;
	}
	for(int i = 0; i < maxn; i++){
		vis[i] = 0;
		for(int j = 0; j < maxn; j++){
			contact[i][j] = 0;
			dis[i][j] = maxd;
		}
	}
}

void dijkstra(int source){
	dis[source][source] = 0;					   // diem hien tai la source
	for(int i = 1; i <= n; i++){           // check tung diem
		int pos = -1;						// tim diem lan can gan nhat cua source
		for(int j = 1; j <= n; j++){       
			if( vis[j] == 0){
				if(pos == -1 || dis[source][j] < dis[source][pos])
					pos = j;
			}
		}
		vis[pos] = 1;
		for(int j = 1; j <= n; j++){
			if(contact[pos][j] != 0 && dis[source][pos] != maxd){     // neu j co lien ket voi pos va pos da xet khoang cach toi source
				if( dis[source][pos] + contact[pos][j] < dis[source][j]){     // neu khoang cach tu source toi j theo duong pos nho hon duong khac da xet
					dis[source][j] = dis[source][pos] + contact[pos][j];
				}
			}
		}
	}
}

void backtrack(int pos, int sum){
	if(sum > ans)
		return;
	if( pos == 1){
		if(sum < ans)
			ans = sum;
		return;
	}
	for(int i = 0; i < n;i++){
		if( dis[pos][i] == maxd)
			continue;
		backtrack(i, sum + dis[pos][i]);
	}
}

void exports(int tc){
	for(int i = 0; i < n; i++){
		dijkstra(i);
	}
	ans = maxd;
	backtrack(1, 0);
	if(ans ==  maxd)
		ans = -1;
	cout << "case #" << tc << endl;
	cout << ans << endl;
}

int main(){
	freopen("input.txt","r",stdin);
	int t;
	cin >> t;
	for(int tc = 1; tc <= t; tc++){
		reset();
		imports();
		exports(tc);
	}
	return 0;
}