fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int Nmax = (1 << 20) + 7;
  5. const int nodemax = 507;
  6. const int MOD = 1000000007;
  7.  
  8. int numnode, k, len;
  9. long long edge[nodemax][nodemax];
  10. vector<int> ship;
  11. long long dp[23][Nmax];
  12. void in(){
  13.     memset(dp, -1, sizeof(dp));
  14.     cin >> numnode >> k;
  15.     for(int i = 1; i <= numnode; i++){
  16.         for(int j = 1; j <= numnode; j++){
  17.             int x;
  18.             cin >> x;
  19.             edge[i][j] = x;
  20.         }
  21.     }
  22.     for(int i = 1; i <= k; i++){
  23.         int x; cin >> x;
  24.         ship.push_back(x);
  25.     } sort(ship.begin(), ship.end());
  26.     len = ship.size();
  27.     for(int k = 1; k <= numnode; k++){
  28. 		for(int i = 1 ; i <= numnode; i++){
  29. 			for(int j = 1 ; j <= numnode; j++){
  30. 				if(edge[i][j] > edge[i][k] + edge[k][j]) edge[i][j] = edge[i][k] + edge[k][j];
  31. 			}
  32. 		}
  33. 	}
  34. }
  35. long long calc(int u, int choose){
  36.     if(choose == (1 << len) - 1){
  37.         long long res = edge[u][1];
  38.         return res;
  39.     }
  40.     long long &res = dp[u][choose];
  41.     if(res != -1) return res;
  42.     res = 1e18;
  43.     for(int i = 0; i < len; i++){
  44.         int v = ship[i];
  45.         int c = edge[u][v];
  46.         if(!((choose >> i) & 1)) {
  47.             res = min(res, 0ll + c + calc(v, choose + (1 << i)));
  48.         }
  49.     }
  50.     return res;
  51. }
  52. void sol(){
  53.     cout << calc(1, 0);
  54. }
  55. int main(){
  56.     freopen("banhkhuc.inp", "r", stdin);
  57.     freopen("banhkhuc.out", "w", stdout);
  58.     ios_base::sync_with_stdio(false);
  59.     cin.tie(0);
  60.     int t = 1;
  61.     //cin >> t;
  62.     while(t--){
  63.        in();
  64.        sol();
  65.     }
  66.     return 0;
  67. }
Success #stdin #stdout 0.07s 193804KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/jYNFVz
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

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!