分析
如果考虑 ,而因为可以向回走,所以状态并不好转移。这里直接考虑最短路算法。走路就是在两两个站中加双向边,而站台就是加从左向右的单向边。
代码
#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; }