NC208342. 上学要迟到了
描述
牛牛早上起床一看，自己睡过了，赶紧起床准备去学校，他去学校只有两种方式，坐公交车和步行，牛牛去学校是一条直线，这条直线上总共有n个车站，车站之间的距离都是相等的，每个车站只有一种公交车，每个公交车只在对应的公交站停车，每个公交车的速度也不一样，第i种公交车过一站的时间需要
，并且公交车是单向行驶，只能从左到到右，走路可以任意走，然而牛牛自己步行走一站需要的时间为T，恰好牛牛家和学校都在某一个站点，分别为s和t，问最少需要多少时间牛牛才能到学校？
输入描述
第一行为正整数
分别表示直线上的车站个数，公交车种数，牛牛家的位置，学校的位置和牛牛自己步行走一站需要的时间
第二行有个正整数表示每种公交车过一站需要的时间为
第三行有
个正整数表示每个车站可停的公交车为
输出描述
输出牛牛从家到学校的最少时间
示例1
输入:
5 3 1 5 10 3 2 1 1 3 2 3 1
输出:
3
说明:
第一种公交车可以从1到5，所以直接乘坐第一种公交车，可以从1到5，第一种公交车没站花费时间为3C++ 解法, 执行用时: 117ms, 内存消耗: 71984K, 提交时间: 2022-06-11 16:26:08
#include<bits/stdc++.h>
using namespace std;
#define N 100005
#define int long long
int n,m,qi,zhong,T,t[N],a[N],xia[N],l[N],f[N],q[N*100],h,tt,x;
signed main(){
scanf("%lld%lld%lld%lld%lld",&n,&m,&qi,&zhong,&T);
for(int i=1;i<=m;i++) scanf("%d",&t[i]);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
xia[l[a[i]]]=i;
l[a[i]]=i;
}
memset(f,9,sizeof(f));
f[qi]=0;
q[h=tt=1]=qi;
while(h<=tt){
x=q[h++];
if(xia[x]&&f[x]+t[a[x]]<f[xia[x]]) f[xia[x]]=f[x]+t[a[x]],q[++tt]=xia[x];
if(x<n&&f[x]+T<f[x+1]) f[x+1]=f[x]+T,q[++tt]=x+1;
if(x>1&&f[x]+T<f[x-1]) f[x-1]=f[x]+T,q[++tt]=x-1;
}
printf("%lld",f[zhong]);
return 0;
}