fork download
  1. /* Author : Nguyen Thanh Tung - Tran Hung Dao High School for Gifted Student */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define ft first
  6. #define sc second
  7. #define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
  8. #define FORD(i, r, l) for(int i = (r); i >= (l); --i)
  9. #define all(x) x.begin(), x.end()
  10. #define int long long
  11. #define endl '\n'
  12.  
  13. #define c_bit(x) __builtin_popcountll(x)
  14. #define MASK(i) ((1) << (i))
  15. #define BIT(x, i) (((x) >> (i)) & 1)
  16. #define ON_BIT(x, i) ((x) | MASK(i))
  17. #define OFF_BIT(x, i) ((x) & ~(MASK(i)))
  18. #define INV_BIT(x, i) ((x) ^ (MASK(i)))
  19.  
  20. using namespace std;
  21.  
  22. typedef pair<int, int> ii;
  23.  
  24. const int N = 17;
  25. const long long oo = 1e18 + 7;
  26. const long long MOD = 1e9 + 7;
  27.  
  28. int n, c[N][N];
  29. int dp[1 << N][N];
  30.  
  31. void solve() {
  32. cin >> n;
  33. FOR(i, 0, n - 1) {
  34. FOR(j, 0, n - 1) {
  35. cin >> c[i][j];
  36. }
  37. }
  38. memset(dp, 0x3f, sizeof(dp));
  39. dp[1][0] = 0;
  40. FOR(mask, 0, MASK(n) - 1) {
  41. FOR(i, 0, n - 1) {
  42. if(!BIT(mask, i)) {
  43. continue;
  44. }
  45. FOR(j, 0, n - 1) {
  46. if(BIT(mask, j)) {
  47. continue;
  48. }
  49. int nbit = ON_BIT(mask, j);
  50. dp[nbit][j] = min(dp[nbit][j], dp[mask][i] + c[i][j]);
  51. }
  52. }
  53. }
  54. cout << *min_element(dp[MASK(n) - 1], dp[MASK(n) - 1] + n);
  55. }
  56.  
  57. #define TASK "code"
  58.  
  59. signed main () {
  60. ios_base::sync_with_stdio (false);
  61. cin.tie(nullptr), cout.tie(nullptr);
  62. if (fopen(TASK".inp", "r")) {
  63. freopen(TASK".inp", "r", stdin);
  64. freopen(TASK".out", "w", stdout);
  65. }
  66. int T = 1;
  67. // cin >> T;
  68. while(T--) {
  69. solve();
  70. }
  71. return 0;
  72. }
  73.  
  74.  
Success #stdin #stdout 0.01s 20992KB
stdin
Standard input is empty
stdout
4557430888798830399