题意

（啊好难总结复制了）
去学校只有两种方式，坐公交车和步行，牛牛去学校是一条直线，这条直线上总共有n个车站，车站之间的距离都是相等的，每个车站只有一种公交车ai，每个公交车只在对应的公交站停车，第i种公交车过一站的时间需要ti，并且公交车是单向行驶，只能从左到到右，走路可以任意走，然而牛牛自己步行走一站需要的时间为T，恰好牛牛家和学校都在某一个站点，分别为s和t，问最少需要多少时间牛牛才能到学校？

题解

建图，存在两种情况

  1. 通过步行到达，任意两点均可，但为了效率，仅对相邻两点填边（双向边）即可
  2. 通过公交车到达，对每个站点记录此站点公交车的上一站，若存在则填边（单向边）。
    建好图直接进行dijkstra求最短路即可

    code

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;

int head[maxn],tot;
struct Edge{
   int v,w;
   int nxt;

   bool operator<(const Edge& x)const{
      return w < x.w;
   }
}edges[maxn << 1];
int busT[maxn];
int a[maxn];
int pre[maxn];
int mp[maxn];
bool vis[maxn];
ll dist[maxn];

void addedge(int u,int v,int w)
{
   edges[tot] = {v,w,head[u]};
   head[u] = tot++;
}

void dij(int s)
{
   priority_queue<pii,vector<pii>,greater<> > pq;
   pq.push({0,s});
   while(!pq.empty()){
      pii hd = pq.top();pq.pop();
      if(vis[hd.second]) continue;
      vis[hd.second] = 1;
      for(int i = head[hd.second];i != -1;i = edges[i].nxt){
         int to = edges[i].v;
         int cost = edges[i].w;
         if(dist[to] > hd.first + cost){
            dist[to] = hd.first + cost;
            pq.push({dist[to],to});
         }
      }
   }
}

int main()
{
   fill(dist,dist + maxn,inf);
   memset(head,-1,sizeof(head));
   tot = 0;
   int n,m,s,t,T;
   cin>>n>>m>>s>>t>>T;
   for(int i = 1;i <= m;++i) cin>>busT[i];
   for(int i = 1;i <= n;++i) cin>>a[i];
   for(int i = 1;i <= n;++i){
      if(!mp[a[i]]) mp[a[i]] = i;
      else{ 
         pre[i] = mp[a[i]];     
         mp[a[i]] = i;
      }
   }
   for(int i = n;i >= 2;--i){
      addedge(i,i-1,T);
      addedge(i-1,i,T);
   }
   for(int i = 1;i <= n;++i){
      if(pre[i]){
         addedge(pre[i],i,busT[a[i]]);
      }
   }
   dij(s);
   printf("%lld\n",dist[t]);
   return 0;
}

求大佬解释为啥dp不能过啊..

dp代码

#include <bits/stdc++.h>
#define reg register
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
#define e exp(1.0)
#define ios ios::sync_with_stdio(false)
#define rep(i,l,r) for(int i=(l);i<(r);i++)
using namespace std;

const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;

ll n,m,s,t,T;
ll busT[maxn];
ll stop[maxn];
ll pre[maxn];
ll dp[maxn];
int mp[maxn];

int main()
{
   memset(pre,-1,sizeof(pre));
   cin>>m>>n>>s>>t>>T;
   for(int i = 1;i <= n;++i) cin>>busT[i];
   for(int i = 1;i <= m;++i) cin>>stop[i];
   for(int i = 1;i <= m;++i){
      if(mp[stop[i]]){
         pre[i] = mp[stop[i]];
      }
      else mp[stop[i]] = i;
   }
   dp[s] = 0;
   for(int i = s-1;i >= 1;--i){    //起点前面的站只能通过步行到达
      dp[i] = dp[i+1] + T;
   }
   for(int i = s+1;i <= m;++i){    //起点后面的站转移，从上一车站或从上一站步行到达
      if(pre[i] == -1) dp[i] = dp[i-1] + T;
      else dp[i] = min(dp[i-1] + T,dp[pre[i]] + busT[stop[i]]);
   }
   printf("%lld\n",dp[t]);
   return 0;
}