fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6. #define li pair <ll, int>
  7.  
  8. using namespace std;
  9.  
  10. const int N = 1e6 + 5;
  11. int a[N], n;
  12. int nxt[N], pre[N];
  13. vector <li> adj[N];
  14. vector <int> pos[26];
  15. ll dist[N], A, B, C, D;
  16.  
  17. void nhap() {
  18.     cin >> n >> A >> B >> C >> D;
  19.     FOR(i, 1, n) {
  20.         char x; cin >> x;
  21.         a[i] = x - 'a';
  22.         pos[a[i]].push_back(i);
  23.     }
  24. }
  25.  
  26. void dijkstra() {
  27.     FOR(i, 1, n) dist[i] = 9e18;
  28.     priority_queue <li, vector <li>, greater <li>> q;
  29.     q.push({0, 1});
  30.     dist[1] = 0;
  31.  
  32.     while (!q.empty()) {
  33.         auto [d, u] = q.top();
  34.         q.pop();
  35.  
  36.         if (d > dist[u]) continue;
  37.  
  38.         for (auto [cost, v] : adj[u]) if (dist[v] > dist[u] + cost) {
  39.             dist[v] = dist[u] + cost;
  40.             q.push({dist[v], v});
  41.         }
  42.     }
  43. }
  44.  
  45. void giai() {
  46.     FOR(i, 1, n) {
  47.         int idx = lower_bound(pos[a[i]].begin(), pos[a[i]].end(), i) - pos[a[i]].begin();
  48.         nxt[i] = (idx + 1 < (int) pos[a[i]].size() ? pos[a[i]][idx + 1] : -1);
  49.         pre[i] = (idx - 1 >= 0 ? pos[a[i]][idx - 1] : -1);
  50.     }
  51.  
  52.     FOR(i, 1, n) {
  53.         if (i + 1 <= n) adj[i].push_back({A, i + 1});
  54.         if (i - 1 >= 1) adj[i].push_back({B, i - 1});
  55.         if (nxt[i] != -1) adj[i].push_back({C, nxt[i]});
  56.         if (pre[i] != -1) adj[i].push_back({D, pre[i]});
  57.     }
  58.  
  59.     dijkstra();
  60.     cout << dist[n];
  61. }
  62.  
  63. int main() {
  64.     ios_base::sync_with_stdio(0);
  65.     cin.tie(0); cout.tie(0);
  66.  
  67.     #define name "test"
  68.  
  69.     if (fopen(name".inp", "r")) {
  70.         freopen(name".inp", "r", stdin);
  71.         freopen(name".out", "w", stdout);
  72.     }
  73.  
  74.     nhap();
  75.     giai();
  76.  
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0.01s 30036KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/3W6XeY
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!