fork(4) download
copy 
  1. #include<stdio.h>
  2. #define MIN(a,b) a<=b?a:b
  3.  
  4. int dp[10000][15],src[110],dest[110],n,m,hmcty;
  5. long long int dist[110][110];
  6. void init()
  7. {
  8.     int i,j;
  9.     for(i=0;i<=n+1;i++)
  10.     for(j=0;j<=n+1;j++)
  11.     {if(i==j) dist[i][j]=0;
  12.     else dist[i][j]=-1;
  13.     }
  14.  
  15.     return ;
  16. }
  17.  
  18. void update()
  19. {
  20.     int i,j,k;
  21.     for(i=0;i<=n-1;i++)
  22.     for(j=0;j<=n-1;j++)
  23.     for(k=0;k<=n-1;k++)
  24.     {
  25.         if(dist[i][k]!=-1 && dist[k][j]!=-1)
  26.         {
  27.             if(dist[i][j]==-1)
  28.             dist[i][j]=dist[i][k]+dist[k][j];
  29.             else
  30.             dist[i][j]=MIN(dist[i][j],dist[i][k]+dist[k][j]);
  31.  
  32.         }
  33.  
  34.  
  35.      }
  36.  
  37.     return ;
  38. }
  39.  
  40. int main()
  41. {
  42.     int i,j,k,u,v,d,z,mask,cnt,count;
  43.     long long int res;
  44.     scanf("%d",&count);
  45.     while(count!=0)
  46.     {
  47.         scanf("%d%d%d",&n,&m,&hmcty);
  48.         hmcty--;
  49.  
  50.         init();
  51.         for(i=1;i<=m;i++)
  52.         {
  53.             scanf("%d%d%d",&u,&v,&d);
  54.             u--;
  55.             v--;
  56.             if(dist[u][v]==-1)
  57.             {
  58.             dist[u][v]=d;
  59.             dist[v][u]=d;
  60.             }
  61.             else
  62.             {
  63.                 dist[u][v]=MIN(dist[u][v],d);
  64.                 dist[u][v]=dist[u][v];
  65.             }
  66.         }
  67.  
  68.         update();         //Applying Floyd-Warshall
  69.  
  70.         scanf("%d",&z);
  71.         j=0;
  72.         for(i=1;i<=z;i++)
  73.         {
  74.             scanf("%d%d%d",&u,&v,&d);
  75.             while(d>0)
  76.             {
  77.                 src[j]=u-1;             //The source city is stored if src[] and destination city is stored in dest[]
  78.                 dest[j]=v-1;
  79.                 j++;
  80.                 d--;
  81.             }
  82.         }
  83.         cnt=j;         //cnt stores total requests made.
  84.  
  85.  
  86.       for(mask=1;mask<=(1<<cnt)-1;mask++)
  87.       {
  88.  
  89.           if(!(mask&(mask-1)))        //if mask is a power of 2
  90.           {
  91.  
  92.               i=0;
  93.               while(!(mask&(1<<i))) i++;
  94.               dp[mask][i]= dist[hmcty][src[i]]+dist[src[i]][dest[i]];
  95.  
  96.           }
  97.           else
  98.           {
  99.               i=0;
  100.               while((1<<i)<=mask)
  101.               {
  102.  
  103.  
  104.                   if(mask&(1<<i))
  105.                   {
  106.  
  107.                       j=0;
  108.                       res=-1;
  109.                       while((1<<j)<=(mask^(1<<i)))   //finding the minimum value for dp[mask][i] considering all j whose bit is set in mask
  110.                       {
  111.  
  112.                           if((mask&(1<<j))&& j!=i)
  113.                           {
  114.  
  115.                                 if(res==-1) res=dp[mask^(1<<i)][j]+dist[dest[j]][src[i]]+dist[src[i]][dest[i]];
  116.                            else res=MIN(res,dp[mask^(1<<i)][j]+dist[dest[j]][src[i]]+dist[src[i]][dest[i]]);
  117.                           }
  118.                           j++;
  119.                       }
  120.  
  121.                       dp[mask][i]=res;
  122.  
  123.                   }
  124.                   i++;
  125.               }
  126.           }
  127.  
  128.  
  129.       }
  130.  
  131.  
  132.       res=dp[mask-1][0]+dist[dest[0]][hmcty];     //dist[dest[i]][hmcty] denotes the shortest distance from destination city of request i to the home city of courier.
  133.      for(i=1;i<=cnt-1;i++)
  134.       res=MIN(res,dp[mask-1][i]+dist[dest[i]][hmcty]);     // Finding the minimum of all (dp[mask-1][i]+ dist[dest[i]][hmcty]).
  135.  
  136.       printf("%lld\n",res);
  137.  
  138.       count--;
  139.     }
  140.  
  141.     return 0;
  142.  
  143. }
  144.  
Success #stdin #stdout 0.01s 2404KB
comments (?)
stdin
copy 
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
copy 
43
https://ideone.com/gHhIjN
language:
C (gcc 8.3)
created:
11 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!