fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int adj[101][101];
  4. vector < pair < int , int > > Orders;
  5. typedef pair < int , int > ii ;
  6. typedef pair < int , ii > iii ;
  7.  
  8. int dp[1<<14][104];
  9.  
  10. const int INF = (int)1e9;
  11.  
  12. int main()
  13. {
  14.     int t;
  15.     scanf("%d",&t);
  16.     for(;t;--t)
  17.     {
  18.         int n , m , b ,  i , j  , u , v , d ;
  19.         int z  , k ;
  20.         int bee;
  21.         scanf("%d%d%d",&n,&m,&bee);
  22.         const int start = bee;
  23.  
  24.  
  25.         for(i=0;i<n;++i)
  26.             for(j=0;j<n;++j)
  27.                 {
  28.                     if(i!=j)
  29.                         adj[i][j] = INF;
  30.                     else
  31.                         adj[i][j] = 0 ;
  32.                 }
  33.  
  34.         for(i=0;i<m;++i)
  35.         {
  36.             scanf("%d%d%d",&u,&v,&d);
  37.             adj[u-1][v-1] = min(d,adj[u-1][v-1]);
  38.             adj[v-1][u-1] = adj[u-1][v-1];
  39.         }
  40.  
  41.         for(k = 0;k<n;++k)
  42.             for(i=0;i<n;++i)
  43.                 for(j=0;j<n;++j)
  44.                         adj[i][j] = min(adj[i][j] , adj[i][k] + adj[k][j]);
  45.         cout<<"\n";
  46.  
  47.  
  48.         for(i=0;i<n;++i,cout<<endl)
  49.             for(j=0;j<n;++j)
  50.                 cout<<adj[i][j]<<" ";
  51.  
  52.  
  53.  
  54.  
  55.         scanf("%d",&z);
  56.  
  57.         for(i=0;i<z;++i)
  58.         {
  59.             scanf("%d%d%d",&u,&v,&d);
  60.             for(j=0;j<d;++j)
  61.                 Orders.push_back(make_pair(u-1,v-1));
  62.         }
  63.  
  64.         int sz = (int)Orders.size();
  65.  
  66.  
  67.         for(i=0;i<=sz;++i)
  68.             for(j=0;j<=(1<<sz);++j)
  69.                             dp[i][j] = INF;
  70.  
  71.         for(i=0;i<sz;++i)
  72.             dp[1<<i][i] = adj[start][Orders[i].first] + adj[Orders[i].first][Orders[i].second];
  73.  
  74.  
  75.         for(i=1; i <(1<<sz) ;++i)
  76.         {
  77.             for(j=0;j<sz;++j)
  78.             {
  79.                 if( __builtin_popcount(i)==1 )
  80.                     {
  81.                         if(!(i&(1<<j)))
  82.                             dp[i][j] = INF;
  83.                         continue;
  84.                     }
  85.  
  86.                 dp[i][j] = INF;
  87.                 if( i&(1<<j) )
  88.                 {
  89.                     int left = i^(1<<j);
  90.                     for(k=0;k<sz;++k)
  91.                     {
  92.                         if(left&(1<<k))
  93.                             dp[i][j] = min(dp[i][j] , dp[left][k] + adj[Orders[k].second][Orders[j].first] + adj[Orders[j].first][Orders[j].second]);
  94.                     }
  95.                 }
  96.             }
  97.         }
  98.  
  99.     int ans = INF;
  100.  
  101.     for(i=0;i<sz;++i)
  102.             ans = min(ans , dp[(1<<sz)-1][i] + adj[Orders[i].second][start]);
  103.  
  104.      printf("%d\n",ans);
  105.  
  106.  
  107.     }
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 0s 10120KB
comments (?)
stdin 
1
5 7 2
1 2 7
1 3 5
1 5 2
2 4 10
2 5 1
3 4 3
3 5 4
3
1 4 2
5 3 1
5 1 1
stdout 
0 3 5 8 2 
3 0 5 8 1 
5 5 0 3 4 
8 8 3 0 7 
2 1 4 7 0 
41
https://ideone.com/FLhsog
language:
C++14 (gcc 8.3)
created:
8 years 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!