Untitled
unknown
plain_text
a year ago
4.9 kB
1
Indexable
Never
// Dijkstra #include <iostream> #define MAX 9223372036854775807 #define ll long long using namespace std; int n, m, k; ll key[1001][1001]; ll visited[1001]; ll arr[1001][1001]; ll arrDL[20]; ll arrHV[20]; ll visitedHV[20]; ll Min; void Dijkstra(int s){ key[s][s] = 0; for(int k=0; k<n; k++){ ll MinD = MAX; int mem = -1; for(int i = 1; i<=n; i++){ if(visited[i] == 0){ if(MinD > key[s][i]){ MinD = key[s][i]; mem = i; } } } if(mem == -1) return; visited[mem] = 1; for(int i=1; i<=n; i++){ if(visited[i] == 0){ if(key[s][i] > key[s][mem] + arr[mem][i] && arr[mem][i] != 0){ key[s][i] = key[s][mem] + arr[mem][i]; } } } } } void BackTrack(int dd, ll sum, int cnt){ if(cnt == k){ if(key[dd][1] == MAX) return; Min = min(Min, sum + key[dd][1]); return; } if(sum >= Min) return; for(int i=1; i<k; i++){ if(visitedHV[i] == 0){ visitedHV[i] = 1; arrHV[cnt] = arrDL[i]; if(key[dd][arrDL[i]] == MAX) return; BackTrack(arrDL[i], sum + key[dd][arrDL[i]], cnt + 1); visitedHV[i] = 0; } } } void reset(int s){ for(int i=1; i<=n; i++){ key[s][i] = MAX; visited[i] = 0; } } void resetBD(){ for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ arr[i][j] = 0; } } for(int i=0; i<=k+1; i++){ visitedHV[i] = 0; arrDL[i] = 0; } } int main(){ //freopen("vao.txt", "r", stdin); int t; cin >> t; for(int tc=1; tc<=t; tc++){ cin >> n >> m >> k; resetBD(); int d; arrDL[0] = 1; for(int i=0; i<k; i++){ cin >> d; arrDL[i+1] = d; } int x, y, w; for(int i=0; i<m; i++){ cin >> x >> y >> w; arr[x][y] = w; } k = k+1; for(int i=0; i<k; i++){ int s = arrDL[i]; reset(s); Dijkstra(s); } Min = MAX; visitedHV[0] = 1; BackTrack(arrDL[0], 0, 1); cout << "Case #" << tc << endl; if(Min != MAX) cout << Min << endl; else cout << "-1" << endl; cout << endl; } return 0; } // BFS #include <iostream> #define ll long long using namespace std; int n, m, k; ll MAX = 9223372036854775807; ll arrDD[1001]; ll key[1001][1001]; ll arr[1001][1001]; ll arrDL[20]; ll visitedBT[1001]; ll visitedBFS[1001]; ll Min; ll arrKe[1001][1001]; ll len[1001]; typedef struct Point{ int x, y, w; }; Point arrTD[1000001]; typedef struct Queue{ int front, rear; Point data[10000001]; }; void init(Queue &Q){ Q.front = Q.rear = -1; } void push(Queue &Q, Point value){ Q.rear++; Q.data[Q.rear] = value; } Point top(int flag, Queue &Q){ Point temp; Q.front++; temp = Q.data[Q.front]; for(int i=Q.front; i<=Q.rear; i++){ int k1 = key[flag][temp.x]; int k2 = key[flag][Q.data[i].x]; if(k1 > k2){ swap(temp.x, Q.data[i].x); } } Q.front--; return temp; } void pop(Queue &Q){ Q.front++; } bool empty(Queue &Q){ if(Q.front == Q.rear) return true; return false; } Queue Q; void BFS(Point P){ init(Q); push(Q, P); visitedBFS[P.x] = 1; key[P.x][P.x] = 0; while(!empty(Q)){ Point P1; P1 = top(P.x, Q); pop(Q); int u = P1.x; for(int i=0; i<len[u]; i++){ int v = arrKe[u][i]; if(visitedBFS[v] == 0 && arr[u][v] != 0){ visitedBFS[v] = 1; key[P.x][v] = key[P.x][u] + arr[u][v]; Point P2; P2.x = v; push(Q, P2); } } } } void BackTrack(int d, ll sum, ll cnt){ if(cnt == k+1){ if(key[d][1] != MAX){ Min = min(Min, sum + key[d][1]); } return; } if(sum >= Min) return; for(int i=1; i<k+1; i++){ int dl = arrDL[i]; if(visitedBT[dl] == 0 && key[d][dl] != MAX){ visitedBT[dl] = 1; BackTrack(dl, sum + key[d][dl], cnt+1); visitedBT[dl] = 0; } } } void resetBFS(int s){ for(int i=1; i<=n; i++){ visitedBFS[i] = 0; } for(int i=1; i<=n; i++){ key[s][i] = MAX; } } void resetBT(){ for(int i=1; i<=n; i++) visitedBT[i] = 0; } void resetBD(){ for(int i=1; i<=n; i++){ arrDD[i] = 0; len[i] = 0; for(int j=1; j<=n; j++) arr[i][j] = 0; } } int main(){ //freopen("vao.txt", "r", stdin); int t; cin >> t; for(int tc=1; tc<=t; tc++){ cin >> n >> m >> k; resetBD(); int d; arrDL[0] = 1; for(int i=0; i<k; i++){ cin >> d; arrDL[i+1] = d; arrDD[d] = 1; } int x, y, w; for(int i=0; i<m; i++){ cin >> x >> y >> w; arrKe[x][len[x]] = y; len[x]++; arr[x][y] = w; } arrDD[1] = 1; for(int i=1; i<=n; i++){ if(arrDD[i] == 1){ int s = i; resetBFS(s); Point P; P.x = i; BFS(P); } } resetBT(); Min = MAX; BackTrack(arrDL[0], 0, 1); cout << "Case #" << tc << endl; if(Min != MAX) cout << Min << endl; else cout << "-1" << endl; cout << endl; } return 0; }