Untitled
unknown
plain_text
2 years ago
6.7 kB
13
Indexable
Tuần trăng mật Đám cưới anh Uranus diễn ra rất vui vẻ, chỉ có Tomoky là có chút hậm hực. Sau đám cưới, anh Uranus muốn đi tuần trăng mật ở thành phố Đà Lạt xinh đẹp. Thành phố Đà Lạt gồm n điểm du lịch trọng điểm, được đánh số từ 1 tới n. Hệ thống giao thông trong vùng gồm m (m <= n*(n-1)) tuyến đường một chiều khác nhau, tuyến đường thứ j (j = 1,2,…m) cho phép đi từ địa điểm u_j tới địa điểm v_j với chi phí đi lại là số nguyên dương c(u_j, v_j). Anh Uranus muốn xuất phát từ điểm du lịch 1 và đi thăm k địa điểm du lịch s_1, s_2, …, s_k (khác địa điểm 1) và sau đó quay về địa điểm xuất phát 1 với tổng chi phí là nhỏ nhất. Cho thông tin về hệ thống giao thông và k địa điểm du lịch s_1, s_2, …, s_k. Hãy giúp anh Uranus xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch 1 và đi thăm k địa điểm s_1, s_2, …, s_k sau đó quay về địa điểm du lịch 1 với tổng chi phí nhỏ nhất. Input • Dòng đầu tiên chứa số nguyên dương T là số bộ test. Mỗi bộ test gồm: • Dòng thứ nhất chứa 3 số nguyên n, m, k (n <= 1000 và k <= 15). • Dòng thứ hai chứa k số nguyên dương s_1, s_2, …, s_k. • Dòng thứ j trong m dòng tiếp theo chứa 3 số nguyên dương u_j, v_j, c(u_j, v_j) cho biết thông tiên về tuyến đường thứ j. Biết rằng u_j luôn khác v_j, và c(u_j, v_j) <= 10^9. Output In ra một số nguyên là tổng chi phí nhỏ nhất tìm được. Nếu không tìm được một hành trình du lịch nào, in ra số -1. Example Input: 1 6 8 2 2 5 1 2 4 2 4 2 4 3 3 3 1 4 4 1 5 3 5 5 5 3 1 5 6 7 Output: 19 Case #1 27 Case #2 57 Case #3 58 Case #4 -1 Case #5 104 Case #6 4381981 Case #7 -1 Case #8 8882702 Case #9 10078253997 Case #10 11212103082 #define _CRT_SECURE_NO_WARNINGS //code 100 #include<iostream> #define oo 99999099 int N, M, K; int arr[1001][1001]; int visited[1001]; int space[1001]; int k[1001]; int arrCanToi[20][20]; int cnt; int sumSpace; int start; int minSpace; using namespace std; void dijictra(int u){ visited[u] = 1; if(k[u] == 1){ arrCanToi[ } for (int i = 1; i <= N; i++) { if(visited[i] == 0 && arr[u][i] != 0){ if(space[u] == oo) space[i] = arr[u][i]; else{ if(space[i] > space[u]+arr[u][i]){ space[i] = space[u]+arr[u][i]; } } } } minSpace = oo; int vt; for (int i = 1; i <= N; i++) { if(space[i] < minSpace && visited[i] == 0){ if(i == 1) continue; minSpace = space[i]; vt = i; } } if(minSpace != oo) dijictra(vt); } void clear(){ for (int i = 1; i <= N; i++) { visited[i] = 0; space[i] = oo; cnt = 0; sumSpace = 0; start = 1; } } int main(int argc, char** argv) { int test_case; int T; int Answer; int u, v, chiphi; freopen("input.txt", "r", stdin); cin >> T; int d; for(test_case = 1; test_case <= T; ++test_case) { Answer = 0; cin >> N >> M >> K; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { arr[i][j] = 0; } k[i] = 0; } for (int i = 1; i <= K; i++) { cin >> d; k[d] = 1; } for (int i = 1; i <= K; i++) { for (int j = 0; j <= K; j++) { arrCanToi[i][j] = 0; } } for (int i = 0; i < M; i++) { cin >> u >> v >> chiphi; arr[u][v] = chiphi; } for (int i = 1; i <= K+1; i++) { clear(); dijictra(k[i]); } if(sumSpace == 0) sumSpace = -1; cout << "Case #" << test_case << endl << sumSpace << endl << endl; } return 0; } #include <iostream> using namespace std; // code 100/100 int dske[1001][1001]; int cost_board[1001][1001]; int visit[1000000]; int nVertex, nEdge, nK_VS; int Need_VS[20]; int Need_Mark[20]; int res; int pay_board[1001][1001]; void input(){ cin >> nVertex >> nEdge >> nK_VS; for(int i = 1; i <= nK_VS; i++){ cin >> Need_VS[i]; } Need_VS[0] = 1; for(int i = 1; i <= nVertex; i++){ dske[i][0] = 0; } for(int i = 1; i <= nVertex; i++){ for(int j = 1; j <= nVertex; j++){ cost_board[i][j] = 9999999; } } for(int i = 0; i < nEdge; i++){ int v1, v2, cost; cin >> v1 >> v2 >> cost; dske[v1][0]++; dske[v1][dske[v1][0]] = v2; cost_board[v1][v2] = cost; } } void dfs(int st, int v1, int v2, int _cost){ if(v1 == v2){ if(_cost < pay_board[st][v2]) pay_board[st][v2] = _cost; return; } if(_cost > pay_board[st][v2]) return; visit[v1] = 1; int nAdj = dske[v1][0]; for(int i = 1; i <= nAdj; i++){ int v_cur = dske[v1][i]; if(visit[v_cur] == 0){ dfs(st,v_cur, v2, _cost + cost_board[v1][v_cur]); } } visit[v1] = 0; } void dijisktra(int s){ for(int i = 1; i <= nVertex; i++){ pay_board[s][i] = 9999999; visit[i] = 0; } pay_board[s][s] = 0; // khoi tao gt ban dau for(int i = 1; i <= nVertex; i++){ int uBest = -1; int minVal = 9999999; //tim dinh chua xet co d min for(int u = 1; u <= nVertex; u++){ if(pay_board[s][u] < minVal && visit[u] == 0){ uBest = u; minVal = pay_board[s][u]; } } // update duong di int u = uBest; visit[u] = 1; for(int v = 1; v <= nVertex; v++){ int temp = pay_board[s][u] + cost_board[u][v]; if(pay_board[s][v] > temp ){ pay_board[s][v] = temp; } } } } void calc_min_cost(){ for(int i = 0; i <= nK_VS; i++){ dijisktra(Need_VS[i]); } } void back_track(int idx, int nVisited, int _cost){ if(nVisited >= nK_VS){ int temp_cost = _cost; if(pay_board[Need_VS[idx]][1] != 9999999){ temp_cost = temp_cost + pay_board[Need_VS[idx]][1]; if(temp_cost < res) res = temp_cost; } return; } if(_cost > res) return; Need_Mark[idx] = 1; for(int i = 1; i <= nK_VS; i++){ if(Need_Mark[i] == 0 && pay_board[Need_VS[idx]][Need_VS[i]] != 9999999){ back_track(i, nVisited + 1, _cost + pay_board[Need_VS[idx]][Need_VS[i]]); } else{ continue; } } Need_Mark[idx] = 0; } int main(){ freopen("input.txt", "r", stdin); int T; cin >> T; for(int tc = 1; tc <= T; tc++){ input(); calc_min_cost(); res = 9999999; back_track(0,0,0); cout << "Case #" << tc << endl; if(res != 0) cout << res << endl << endl; else cout << -1<< endl << endl; } return 0; }
Editor is loading...
Leave a Comment