题目链接

https://ac.nowcoder.com/acm/contest/7412/H

解题思路

单源最短路径问题 Dijkstra算法 需要优先队列优化
这是我写的模板与讲解

问题转化

我们尝试这把这个题对应转化成单源最短路径问题。
S1：每个车站就代表图中的每个点；
S2：每种公交车能停车的地方就是单向可达的，就可以在图中表现为有向边。注意一点，我们要存的有向边并非每个车站到其后面所有能停车的车站的有向边，而是与之相邻的可停车站的有向边，比如1 2 2 1 2 1 1 2 1，对于第一个位置的1车而言，我们只需要将其与第四个位置的1车构建一条单向边即可，不需要与第六个位置的1车构建有向边，因为只要构建好相邻可停车站的有向边，可以通过状态的转移自然构建好，这就是Dijkstra算法完成的事，所以你就没必要做了；
S3：因为可以步行，而且步行可以往回走，这样相当于对于相邻的车站，都可以相互可达，体现在图上，任意相邻两点有一条双向边。

任务分析

create函数要做的，就是实现输入和完成图的构造；
Dijkstra函数是不变的，任务就是不断刷新最短路径；
output函数，输出。
因此，现在我们面临的问题只有如何构建这个图了，也就是create函数的完成。

create函数

正常的输入每种车经过每一站需要的时间；
我们要思考如何把相邻（并非绝对相邻，而是忽略其他类型的车后相对位置相邻）的同型公交车之间构建一条边，并保存在G中。
我想到了用vector去存储相同类型车的车站位置，之后循环每种公交车对应的车站位置，把相邻的构建一条边，压入G中就行了。
所以，我建立了个二维vector，vector<int> car[N]，car[i].size()表示型号为i的汽车能停靠的车站位置的总数，car[i][j]表示型号为i的汽车第j-1个停靠位置，循环所有的类型汽车的所有的j，把相邻位置构建一下就行了。
对于步行的边的构建就比较好说了吧，输入一个构建一个就行，注意是双向。</int>

AC代码

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1e5+100;
int d[N];
typedef pair<int,int> P;
struct edge{
    int to,cost;
};
int a[N],tme[N];
int n,m,s,t,T;
vector<edge> G[N];
vector<int> car[N];
void create(){
    cin>>n>>m>>s>>t>>T;
    for(int i=1;i<=m;i++) cin>>tme[i];//类型为i的汽车经过一站需要的时间
    for(int i=1;i<=n;i++) {
        cin>>a[i];//每个位置的车型
        car[a[i]].pb(i);//car二维vector的构建
        if(i!=1){//从第二个位置开始构建步行边
            edge tmp;
            tmp.cost=T;tmp.to=i;
            G[i-1].pb(tmp);//从i-1到i构建一条边
            tmp.to=i-1;
            G[i].pb(tmp);//从i到i-1构建一条边
        }                        
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<car[i].size();j++){
            edge tmp;
            tmp.to=car[i][j];tmp.cost=tme[i];
            G[car[i][j-1]].pb(tmp);//相邻同型车停靠车站的边的构造
        }
    fill(d+1,d+n+1,INF);
}
void Dijkstra(){
    priority_queue<P, vector<P>, greater<P> > que;
    que.push(P(0,s));
    d[s]=0;
    while(!que.empty()){
        P p=que.top();que.pop();
        int v=p.second;
        if(d[v]!=p.first) continue;
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}
void output(){
    cout<<d[t]<<endl;
}
void solve(){
    create();
    Dijkstra();
    output();
}
int main(){
    solve();
}