Untitled
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...