分析

如果考虑 ，而因为可以向回走，所以状态并不好转移。这里直接考虑最短路算法。走路就是在两两个站中加双向边，而站台就是加从左向右的单向边。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10,inf = 0x3f3f3f3f;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
struct Node{
    int dis,pos;
    bool operator <(const Node x) const {
        return dis > x.dis;
    }
};
priority_queue<Node> heap;
struct Edge{int to,nxt,w;}e[N<<1];
int n,m,s,t,T,head[N],dis[N],vis[N],D[N],ecnt;
vector<int> Id[N];
void add(int x,int y,int c) {
    e[++ecnt].to = y;e[ecnt].w = c;e[ecnt].nxt = head[x];head[x] = ecnt;
}
void solve(int S) {
    memset(dis,0x3f,sizeof(dis));dis[S] = 0;heap.push((Node){0,S});
    while(heap.size()) {
        int x = heap.top().pos;heap.pop();
        if(vis[x]) continue;vis[x] = 1;
        for(int i = head[x];i;i = e[i].nxt) {
            int y = e[i].to;if(dis[y] > dis[x] + e[i].w) {
                dis[y] = dis[x] + e[i].w;
                heap.push((Node){dis[y],y});
            }
        }
    }
}
int main() {
    n = read();m = read();s = read();t = read();T = read();
    for(int i = 1;i < n;i++) {
        add(i,i+1,T);add(i+1,i,T);
    }
    for(int i = 1;i <= m;i++) D[i] = read();
    for(int i = 1;i <= n;i++) {
        int op = read();Id[op].push_back(i);
    }
    for(int i = 1;i <= m;i++) {
        for(int j = 1;j < Id[i].size();j++) {
            add(Id[i][j-1],Id[i][j],D[i]);
        }
    }
    solve(s);
    cout << dis[t] << endl;
    return 0;
}