fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define li pair<long long , int>
  10. #define iii pair<pair<int , int> , int>
  11. #define db double
  12. #define onBit(mask , i) (mask | (1 << i))
  13. #define offBit(mask , i) (mask & (~(1 << i)))
  14.  
  15. const long long MOD = 1e9 + 7;
  16. const int INF = 8e7;
  17. const int N = 1e3 + 7;
  18. const int S = 252;
  19. vector<char> a[N];
  20. int c[N][S];
  21. string s;
  22. int n;
  23. vector<int> adj[N];
  24. int dist[N][N];
  25.  
  26. void ktao(){
  27.     for (int v = 0 ; v < s.size() ; ++v){
  28.         for (int u = 1 ; u <= n ; ++u){
  29.             int i = 1 , j = v;
  30.             while (i < a[u].size() && j < s.size()){
  31.                 if (a[u][i] == s[j]) ++j;
  32.                 ++i;
  33.             }
  34.             c[u][v] = j - v;
  35.         }
  36.     }
  37.     for (int i = 1 ; i <= n ; ++i){
  38.         for (int j = 1 ; j <= n ; ++j){
  39.             if (a[i][a[i].size() - 1] == a[j][0]) adj[i].push_back(j);
  40.         }
  41.     }
  42. }
  43.  
  44. int calc(int u){
  45.     int i = 0 , j = 0;
  46.     while (i < a[u].size() && j < s.size()){
  47.         if (a[u][i] == s[j]) ++j;
  48.         ++i;
  49.     }
  50.     return j;
  51. }
  52.  
  53. void inp(){
  54.     cin >> s;
  55.     cin >> n;
  56.     for (int i = 1 ; i <= n ; ++i){
  57.         string x;
  58.         cin >> x;
  59.         for (char c : x) a[i].push_back(c);
  60.     }
  61.     ktao();
  62. }
  63.  
  64. void dijkstra(){
  65.     for (int i = 1 ; i <= n ; ++i){
  66.         for (int j = 1 ; j <= s.size() ; ++j){
  67.             dist[i][j] = INF;
  68.         }
  69.     }
  70.     priority_queue<iii , vector<iii> , greater<iii>> pq;
  71.     for (int i = 1 ; i <= n ; ++i){
  72.         int tmp = calc(i);
  73.         dist[i][tmp] = a[i].size();
  74.         pq.push({{a[i].size() , tmp} , i});
  75.     }
  76.  
  77.  
  78.     while (pq.size()){
  79.         iii val = pq.top();
  80.         pq.pop();
  81.  
  82.         int d_u = val.fi.fi , cnt = val.fi.se , u = val.se;
  83.         if (cnt == s.size()) continue;
  84.         if (d_u > dist[u][cnt]) continue;
  85.  
  86.         for (int v : adj[u]){
  87.             int w = a[v].size() - 1 , n_cnt = cnt + c[v][cnt];
  88.             if (dist[v][n_cnt] > dist[u][cnt] + w){
  89.                 dist[v][n_cnt] = dist[u][cnt] + w;
  90.                 pq.push({{dist[v][n_cnt] , n_cnt} , v});
  91.             }
  92.         }
  93.     }
  94. }
  95.  
  96. void solve(){
  97.     dijkstra();
  98.     int res = INF;
  99.     for (int j = 1 ; j <= n ; ++j)
  100.         res = min(res , dist[j][s.size()]);
  101.     if (res == INF) cout << -1;
  102.     else cout << res;
  103. }
  104.  
  105. int main(){
  106. //    freopen("xhmax.inp" , "r" , stdin);
  107. //    freopen("xhmax.out" , "w" , stdout);
  108.     faster;
  109.     inp();
  110.     solve();
  111.     return 0;
  112. }
  113.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/YxdHwP
language:
C++14 (gcc 8.3)
created:
6 days 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!