fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define pub push_back
  7. #define pob pop_back
  8. #define mpa make_pair
  9. const int maxn = 1e6 + 10;
  10. int n;
  11. struct value{
  12.     int a, b, c, d;
  13. };
  14. value cost;
  15. int posL[36], posR[36];
  16. int L[maxn], R[maxn];
  17. string s;
  18. vector<pair<int, int>> a[maxn];
  19. ll d[maxn];
  20. void dij()
  21. {
  22.     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  23.     memset(d, 0x3f, sizeof d);
  24.     d[1] = 0;
  25.     pq.push({0, 1});
  26.     while(!pq.empty())
  27.     {
  28.         pair<ll, int> top = pq.top(); pq.pop();
  29.         int u = top.se;
  30.         ll len = top.fi;
  31.         if(d[u] != len) continue;
  32.         if(u == n)
  33.         {
  34.             cout << d[u];
  35.             return ;
  36.         }
  37.         for(pair<int, int> ii : a[u])
  38.         {
  39.             int v = ii.fi;
  40.             int w = ii.se;
  41.             if(d[v] > d[u] + w)
  42.             {
  43.                 d[v] = d[u] + w;
  44.                 pq.push({d[v], v});
  45.             }
  46.         }
  47.     }
  48.     cout << d[n];
  49. }
  50. int main()
  51. {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(0);
  54.     cout.tie(0);
  55.     #define code code
  56. //    freopen("code.INP","r",stdin);
  57. //    freopen("code.OUT","w",stdout);
  58.     cin >> n;
  59.     cin >> cost.a >> cost.b >> cost.c >> cost.d;
  60.     cin >> s;
  61.     s = ' ' + s;
  62.     for(int i=1; i<=n; i++)
  63.     {
  64.         L[i] = posL[s[i] - 'a'];
  65.         posL[s[i] - 'a'] = i;
  66.     }
  67.     for(int i=n; i>=1; i--)
  68.     {
  69.         R[i] = posR[s[i] - 'a'];
  70.         posR[s[i] - 'a'] = i;
  71.     }
  72.     for(int i=1; i<n; i++)
  73.     {
  74.         a[i].pub({i + 1, cost.a});
  75.         a[i + 1].pub({i, cost.b});
  76.     }
  77.     for(int i=1; i<=n; i++)
  78.     {
  79.         if(R[i] != 0)
  80.         {
  81.             a[i].pub({R[i], cost.c});
  82.         }
  83.         if(L[i] != 0)
  84.         {
  85.             a[i].pub({L[i], cost.d});
  86.         }
  87.     }
  88.     dij();
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 0.01s 36356KB
comments (?)
stdin 
Standard input is empty
stdout 
4557430888798830399
https://ideone.com/zJvc3w
language:
C++14 (clang 8.0)
created:
16 hours 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!