fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. int main()
  6. {
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(0);
  9.  
  10.     ll t;
  11.     cin>>t;
  12.  
  13.     while (t--)
  14.     {
  15.         ll n,m;
  16.         cin>>n>>m;
  17.         ll k;
  18.         cin>>k;
  19.         vector <string> v(k+2);
  20.         for (ll i=1;i<=k;i++)
  21.         {
  22.             cin>>v[i];
  23.         }
  24.         vector <vector <pair<ll,ll>>> g(2*n*m+1);
  25.         for (char ch='a';ch<=('a'+(m-1));ch++)
  26.         {
  27.             for (ll num=1;num<=n;num++)
  28.             {
  29.                 ll nd_num=(ch-'a')*(2*n);
  30.                 nd_num+=((num-1)*2);
  31.                 nd_num++;
  32.                 ll num1=num;
  33.                 char ch1=ch;
  34.                     num1++;
  35.                     ch1--;
  36.                     while (num1<=n && ch1>='a')
  37.                     {
  38.                         ll nd_num1=(ch1-'a')*(2*n);
  39.                         nd_num1+=(num1-1)*2;
  40.                         nd_num1++;
  41.                         g[nd_num].push_back({nd_num1,0});
  42.                         num1++;
  43.                         ch1--;
  44.                     }
  45.                     num1=num;
  46.                     ch1=ch;
  47.                     num1--;
  48.                     ch1++;
  49.                     while (num1>=1 && ch1<=('a'+(m-1)))
  50.                     {
  51.                         ll nd_num1=(ch1-'a')*(2*n);
  52.                         nd_num1+=(num1-1)*2;
  53.                         nd_num1++;
  54.                         g[nd_num].push_back({nd_num1,0});
  55.                         num1--;
  56.                         ch1++;
  57.                     }
  58.                 nd_num++;
  59.                 num1=num;
  60.                 ch1=ch;
  61.                     num1++;
  62.                     ch1++;
  63.                     while (num1<=n && ch1<=('a'+(m-1)))
  64.                     {
  65.                         ll nd_num1=(ch1-'a')*(2*n);
  66.                         nd_num1+=(num1)*2;
  67.                         g[nd_num].push_back({nd_num1,0});
  68.                         num1++;
  69.                         ch1++;
  70.                     }
  71.                     num1=num;
  72.                     ch1=ch;
  73.                     num1--;
  74.                     ch1--;
  75.                     while (num1>=1 && ch1>='a')
  76.                     {
  77.                         ll nd_num1=(ch1-'a')*(2*n);
  78.                         nd_num1+=(num1)*2;
  79.                         g[nd_num].push_back({nd_num1,0});
  80.                         num1--;
  81.                         ch1--;
  82.                     }
  83.                 nd_num--;
  84.                 g[nd_num].push_back({nd_num+1,1});
  85.                 g[nd_num+1].push_back({nd_num,1});
  86.             }
  87.         }
  88.         map <ll,vector <ll>> dist_vectors;
  89.         for (ll i=1;i<=k;i++)
  90.         {
  91.             char ch=v[i][0];
  92.             string str=v[i].substr(1);
  93.             ll r_num=stoll(str);
  94.             ll nd_num=(ch-'a')*(2*n);
  95.             nd_num+=(r_num-1)*2;
  96.             nd_num++;
  97.             dist_vectors[nd_num].resize(2*n*m+1,LLONG_MAX);
  98.             dist_vectors[nd_num+1].resize(2*n*m+1,LLONG_MAX);
  99.         }
  100.         dist_vectors[2].resize(2*n*m+1,LLONG_MAX);
  101.         set <pair<ll,ll>> s;
  102.         vector <bool> visited(2*n*m+1,false);
  103.         s.insert({0,2});
  104.         dist_vectors[2][2]=0;
  105.         while (!s.empty())
  106.         {
  107.             auto elem=s.begin();
  108.             ll nd=(*elem).second;
  109.             if (visited[nd])
  110.             {
  111.                 s.erase(elem);
  112.                 continue;
  113.             }
  114.             ll w=(*elem).first;
  115.             visited[nd]=true;
  116.             s.erase(elem);
  117.             for (auto child:g[nd])
  118.             {
  119.                 if (!visited[child.first] && dist_vectors[2][child.first]>(child.second+w))
  120.                 {
  121.                     dist_vectors[2][child.first]=(child.second+w);
  122.                     s.insert({dist_vectors[2][child.first],child.first});
  123.                 }
  124.             }
  125.         }
  126.         for (ll i=1;i<=k;i++)
  127.         {
  128.             char ch=v[i][0];
  129.             string str=v[i].substr(1);
  130.             ll r_num=stoll(str);
  131.             ll nd_num=(ch-'a')*(2*n);
  132.             nd_num+=(r_num-1)*2;
  133.             nd_num++;
  134.             vector <bool> vis(2*n*m+1,false);
  135.             s.insert({0,nd_num});
  136.             dist_vectors[nd_num][nd_num]=0;
  137.             while (!s.empty())
  138.             {
  139.                 auto elem=s.begin();
  140.                 ll nd=(*elem).second;
  141.                 if (vis[nd])
  142.                 {
  143.                     s.erase(elem);
  144.                     continue;
  145.                 }
  146.                 ll w=(*elem).first;
  147.                 vis[nd]=true;
  148.                 s.erase(elem);
  149.                 for (auto child:g[nd])
  150.                 {
  151.                     if (!vis[child.first] && dist_vectors[nd_num][child.first]>(child.second+w))
  152.                     {
  153.                         dist_vectors[nd_num][child.first]=(child.second+w);
  154.                         s.insert({dist_vectors[nd_num][child.first],child.first});
  155.                     }
  156.                 }
  157.             }
  158.             nd_num++;
  159.             vector <bool> vis1(2*n*m+1,false);
  160.             s.insert({0,nd_num});
  161.             dist_vectors[nd_num][nd_num]=0;
  162.             while (!s.empty())
  163.             {
  164.                 auto elem=s.begin();
  165.                 ll nd=(*elem).second;
  166.                 if (vis1[nd])
  167.                 {
  168.                     s.erase(elem);
  169.                     continue;
  170.                 }
  171.                 ll w=(*elem).first;
  172.                 vis1[nd]=true;
  173.                 s.erase(elem);
  174.                 for (auto child:g[nd])
  175.                 {
  176.                     if (!vis1[child.first] && dist_vectors[nd_num][child.first]>(child.second+w))
  177.                     {
  178.                         dist_vectors[nd_num][child.first]=(child.second+w);
  179.                         s.insert({dist_vectors[nd_num][child.first],child.first});
  180.                     }
  181.                 }
  182.             }
  183.         }
  184.         ll answer=LLONG_MAX;
  185.         for (ll i=0;i<=(((1LL)<<k)-1);i++)
  186.         {
  187.             vector <ll> store;
  188.             ll ind=1;
  189.             for (ll j=1;j<=((1LL)<<(k-1));j*=2)
  190.             {
  191.                 if ((i&j))
  192.                 {
  193.                     char ch=v[ind][0];
  194.                     string str=v[ind].substr(1);
  195.                     ll r_num=stoll(str);
  196.                     ll nd_num=(ch-'a')*(2*n);
  197.                     nd_num+=(r_num-1)*2;
  198.                     nd_num++;
  199.                     store.push_back(nd_num);
  200.                 } else 
  201.                 {
  202.                     char ch=v[ind][0];
  203.                     string str=v[ind].substr(1);
  204.                     ll r_num=stoll(str);
  205.                     ll nd_num=(ch-'a')*(2*n);
  206.                     nd_num+=(r_num)*2;
  207.                     store.push_back(nd_num);
  208.                 }
  209.                 ind++;
  210.             }
  211.             sort(store.begin(),store.end());
  212.             do 
  213.             {
  214.                 ll temp=0;
  215.                 ll sz=k;
  216.                 temp+=(dist_vectors[2][store[0]]);
  217.                 for (ll j=1;j<sz;j++)
  218.                 {
  219.                     temp+=(dist_vectors[store[j-1]][store[j]]);
  220.                 }
  221.                 answer=min(answer,temp);
  222.             } while (next_permutation(store.begin(),store.end()));
  223.         }
  224.         cout<<answer<<"\n";
  225.     }
  226.  
  227.     return 0;
  228. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
1
8 8
1
g1
stdout
copy 
1
https://ideone.com/kq7nXk
language:
C++14 (clang 8.0)
created:
228 days ago
visibility:
secret

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!