Untitled
plain_text
a month ago
3.6 kB
2
Indexable
Never
#include<iostream> using namespace std; int TC, N, M, K, a[1005][1005], c[1005][1005], b[20], vi[1005], di[1005], pa[1005], vib[20], hv[20], minre, dp[1005][1005]; int int_max = 2147483647; int mind() { int mink = int_max, mini = -1; for(int i = 0; i < N; i++) { if(vi[i] == 0 && di[i] < mink) { mink = di[i], mini = i; } } return mini; } int findMind(int x, int y) { fill_n(di, N, int_max); fill_n(vi, N, 0); fill_n(pa, N, -1); di[x] = 0; for(int i = 0; i < N - 1; i++) { int id = mind(); if(id == -1) break; vi[id] = 1; for(int j = 1; j <= a[id][0]; j++) { if(vi[ a[id][j] ] == 0 && di[id] != int_max && di[id] + c[id][j] < di[ a[id][j] ]) { di[ a[id][j] ] = di[id] + c[id][j]; pa[ a[id][j] ] = id; } } } int kc = di[y] == int_max ? -1 : di[y]; for(int i = 0; i < N; i++) { if(di[i] != int_max) { dp[x][i] = di[i]; } } //int tmp = y; //while(pa[y] != -1) { // for(int i = 0; i < ) // pa[y]; //} return kc; } void doing(int k, int c, int pre) { if(c >= minre) return; if(k == K) { /*for(int i = 0; i < K; i++) { cout << b[hv[i]] << " "; } cout << endl;*/ int tmpc; if(dp[b[pre]][0] == -1) { tmpc = findMind(b[pre], 0); } else { tmpc = dp[b[pre]][0]; } if(c + tmpc < minre) minre = c + tmpc; return; } for(int i = 0; i < K; i++) { if(vib[i] == 0) { //hv[k] = i; int ch = 1; int tmpd; if(k == 0) { if(dp[0][b[i]] == -1) { tmpd = findMind(0, b[i]); if(tmpd == -1) { ch = 0; } } else { tmpd = dp[0][b[i]]; } } else { if(dp[b[pre]][b[i]] == -1) { tmpd = findMind(b[pre], b[i]); if(tmpd == -1) { ch = 0; } } else { tmpd = dp[b[pre]][b[i]]; } } if(ch == 1) { vib[i] = 1; doing(k + 1, c + tmpd, i); vib[i] = 0; } } } } int main() { freopen("input.txt", "r", stdin); cin >> TC; for(int tc = 1; tc <= TC; tc++) { cin >> N >> M >> K; for(int i = 0; i < K; i++) cin >> b[i]; for(int i = 0; i < K; i++) b[i]--; fill_n(vib, K, 0); for(int i = 0; i < N; i++) fill_n(dp[i], N, -1); for(int i = 0; i < M; i++) { int x, y, ci; cin >> x >> y >> ci; x--, y--; a[x][0]++; a[x][a[x][0]] = y, c[x][a[x][0]] = ci; } minre = int_max; /*cout << "HJ " << findMind(0, 1) << endl; cout << "HJ " << findMind(1, 4) << endl; cout << "HJ " << findMind(4, 0) << endl; cout << "HJ " << findMind(0, 4) << endl; for(int i = 0; i < N; i++) { cout << pa[i] << " " ; } cout << endl; cout << "HJ " << findMind(4, 1) << endl; cout << "HJ " << findMind(1, 0) << endl;*/ doing(0, 0, -1); minre = minre == int_max ? -1 : minre; cout << "Case #" << tc << endl << minre << endl << endl; } return 0; }