蓝桥杯2022年第十三届决赛真题-出差

解题思路:将时间和隔离时间的和算作这条路的代价，并用朴素的单源最短路dijkstra算法求出最短路即可

注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int N=1e3+10,M=2e5+10;

struct rec{

 int s;

 int e;

 int cost;

}edge[M];

int nex[M],head[N],geli[N],n,m,dj[N],v[N];            //单源最短路，迪杰斯特拉

void push(int i,int num)        //存储编号为num的边

{

    nex[num]=head[i];

    head[i]=num;

}

int main()

{

    cin>>n>>m;

    memset(head,0,sizeof(head));

    memset(dj,0x3f3f3f3f,sizeof(dj));

    memset(v,0,sizeof(v));

    int in=0;      //edge数组的下标

    for(int i=1;i<=n;i++) cin>>geli[i];

    for(int i=1;i<=m;i++)

    {

        int s,e,cost;

        cin>>s>>e>>cost;

        ++in;

        edge[in].s=s;

        edge[in].e=e;

        edge[in].cost=cost;

        if(e!=n) edge[in].cost+=geli[e];

        push(s,in);

        ++in;

        edge[in].s=e;

        edge[in].e=s;

        edge[in].cost=cost;

        if(s!=n) edge[in].cost+=geli[s];

        push(e,in);

    }                                          //存储图

    dj[1]=0;

    for(int i=1;i<=n;i++)

    {

        int jilu=-1,mi=0x3f3f3f3f;

        for(int k=1;k<=n;k++)       //扩展点

        {

            if(dj[k]<mi&&v[k]==0)

            {

                jilu=k;

                mi=dj[k];

            }

        }

        v[jilu]=1;                   //扩展

        for(int j=head[jilu];j!=0;j=nex[j])

        {

            if(dj[jilu]+edge[j].cost<dj[edge[j].e])

            {

                dj[edge[j].e]=dj[jilu]+edge[j].cost;

            }

        }

    }

    cout<<dj[n]<<endl;

    return 0;

}