fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty