上学要迟到了

  • 前言

    没想到此题甚水

  • 分析

    这道题的思路很好想，因为一个车站只对应三种选择——步行去下一个站，步行去上一个站，坐车去这辆车的下

    一个停靠点，建边跑最短路就完了

  • 代码

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

int n,m,s,t,T,tot;
int a[N],pri[N],col[N],val[N<<2];
int h[N],nex[N<<2],ver[N<<2],dis[N];

bool vis[N];

inline void add(int x,int y,int z)
{
    nex[tot]=h[x];
    ver[tot]=y;
    val[tot]=z;
    h[x]=tot++;
}

inline void dfs(int kl)
{
    queue<int>q;
    vis[kl]=1;dis[kl]=0;
    q.push(kl);
    while(!q.empty())
    {
        int k=q.front();q.pop();
        for (int i=h[k];~i;i=nex[i])
        {
            int j=ver[i];
            if(dis[j]>dis[k]+val[i])
            {
                dis[j]=dis[k]+val[i];
                if(!vis[j])
                    vis[j]=1,q.push(j);
            }
        }vis[k]=0;
    }
}

int main()
{
    memset(h,-1,sizeof(h));
    memset(dis,0x3f,sizeof(dis));

    scanf("%d%d%d%d%d",&n,&m,&s,&t,&T);
    for (int i=1;i<=m;i++) scanf("%d",&pri[i]);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++)
    {
        if(i!=1) add(i,i-1,T);
        if(i!=n) add(i,i+1,T);
        if(col[a[i]]) add(col[a[i]],i,pri[a[i]]);
        col[a[i]]=i;
    }

    dfs(s);

    printf("%d\n",dis[t]);

    return 0;
}