H 上学要迟到了

H 上学要迟到了

最短路的板子题。
建图方法用的链式前向星，输入车站能停什么车时，用了链表的思维，数组就是代表，目前最后这个车可以停在哪个站。将老的能停什么车作为下标，几站作为值，每次更新即可。最后再从到，建走路的双向边。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define rint register int
#define ld long double
#define db double
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define rep1(i, a, n) for (rint i = a; i < n; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define per1(i ,a, n) for (rint i = a; i > n; i--)
namespace IO{
    char ibuf[1<<21],*ip=ibuf,*ip_=ibuf;
    char obuf[1<<21],*op=obuf,*op_=obuf+(1<<21);
    inline char gc(){
        if(ip!=ip_)return *ip++;
        ip=ibuf;ip_=ip+fread(ibuf,1,1<<21,stdin);
        return ip==ip_?EOF:*ip++;
    }
    inline void pc(char c){
        if(op==op_)fwrite(obuf,1,1<<21,stdout),op=obuf;
        *op++=c;
    }
    inline int read(){
        register int x=0,ch=gc(),w=1;
        for(;ch<'0'||ch>'9';ch=gc())if(ch=='-')w=-1;
        for(;ch>='0'&&ch<='9';ch=gc())x=x*10+ch-48;
        return w*x;
    }
    template<class I>
    inline void write(I x){
        if(x<0)pc('-'),x=-x;
        if(x>9)write(x/10);pc(x%10+'0');
    }
    class flusher_{
    public:
        ~flusher_(){if(op!=obuf)fwrite(obuf,1,op-obuf,stdout);}
    }IO_flusher;
}
using namespace IO;


const int N=1e7+10;
const int inf=0x3f3f3f3f;
struct sa{
    int dis;
    int pos;
};
bool operator <(const sa &a,const sa &b) { return a.dis>b.dis; }

priority_queue<sa>q;


struct Edge
{
    int u, v, w, next;
}edge[N<<2];
int head[N];
int cnt;
void add_edge(int u, int v, int w)
{
    edge[cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}


int dis[N],a[N],b[N],pre[N];
bool vis[N];
int n,m,s,t,u,v,w,T;

void dij(int s,int v,int d[]){
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;i++) d[i] = inf;
    d[s]=v;
    q.push( (sa) {v,s});
    while(!q.empty())
    {
        sa ns=q.top();
        q.pop();
        int x=ns.pos;
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x]; i!=-1 ; i=edge[i].next)
        {
            int to=edge[i].v;
            int dd=d[x]+edge[i].w;
            if(d[to]>dd)
            {
                d[to]=dd;
                q.push( (sa) {d[to],to});
            }
        }
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    n=read();m=read();s=read();t=read();T=read();
    rep(i, 1, m) a[i]=read();
    rep(i, 1, n){
        b[i]=read();
        if(pre[b[i]]) add_edge(pre[b[i]],i,a[b[i]]);
        pre[b[i]]=i;
    }
    rep1(i, 1, n){
        add_edge(i,i+1,T);
        add_edge(i+1,i,T);
    }
    dij(s,0,dis);
    write(dis[t]);
    return 0;
}