fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. template<typename T>
  11. void minimize(T& a, const T& b) {
  12. 	if (b < a) a = b; 
  13. }
  14.  
  15. int n;  
  16. int C[15][15];  
  17. int dp[1 << 15][15]; // dp[mask][i]: Chi phí rẻ nhất của đường đi đã đi qua các nước trong tập mask,
  18. 					 // mỗi đất nước đi qua đúng một lần và dừng chân tại đất nước i
  19.  
  20. int main() {
  21. 	ios::sync_with_stdio(0); cin.tie(0);  	
  22. 	cin >> n; 
  23. 	for (int i = 0; i < n; i++) {
  24. 		for (int j = 0; j < n; j++) cin >> C[i][j]; 
  25. 	}
  26.  
  27. 	for (int mask = 0; mask < (1 << n); mask++) {
  28. 		for (int i = 0; i < n; i++) dp[mask][i] = INF; 
  29. 	}
  30.  
  31. 	for (int i = 0; i < n; i++) dp[1 << i][i] = 0; 
  32.  
  33. 	for (int mask = 0; mask < (1 << n); mask++) {
  34. 		for (int i = 0; i < n; i++) {
  35. 			if (dp[mask][i] == INF) continue;  
  36.  
  37. 			for (int j = 0; j < n; j++) {
  38. 				if (mask & (1 << j)) continue; 
  39. 				int new_mask = mask | (1 << j); 
  40. 				minimize(dp[new_mask][j], dp[mask][i] + C[i][j]); 
  41. 			}
  42. 		}
  43. 	}
  44.  
  45. 	int ans = INF; 
  46. 	for (int i = 0; i < n; i++) {
  47. 		minimize(ans, dp[(1 << n) - 1][i]); 
  48. 	}
  49.  
  50. 	cout << ans << '\n';
  51. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
6
0 1 2 1 3 4 
5 0 3 2 3 4 
4 1 0 2 1 2 
4 2 5 0 4 3 
2 5 3 5 0 2 
5 4 3 3 1 0
stdout
copy 
8
https://ideone.com/Q00vUd
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!