P8802 [蓝桥杯 2022 国 B] 出差 题解

· · 题解

Dijkstra 堆优化 + vector 存图

看到各位 dalao 都用链式前向星，奈何我不会，所以写一篇用 vector 存的。

思路：

注意到是单源最短路，且没有负边权，选择 Dijkstra。

隔离的时间可以丢进路线的时间里，具体操作如下：

每条路的边权=原来的边权+目的地的点权。

这样就转化成了一个 Dijkstra 板子题。

（温馨提示：因为目的地不需要隔离，所以输出时减去城市 N 的隔离时间）

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int maxn=1e5+5,inf=0x3f3f3f3f;
int n,m,add[maxn],dis[maxn];
bool vis[maxn]={0};
vector<pii> G[maxn];
void dijkstra()//Dijkstra 
{
    for(int i=1;i<=n;i++) dis[i]=inf,vis[i]=0;
    dis[1]=0;
    priority_queue<pii,vector<pii>,greater<pii> >p;//堆优化 
    p.push({0,1});
    while(!p.empty())
    {
        int u=p.top().second;
        p.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=0;i<G[u].size();i++)
        {
            int cost=G[u][i].second,v=G[u][i].first;
            if(dis[v]>dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
                p.push({dis[v],v});
            }
        } 
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>add[i];
    for(int i=1;i<=m;i++)
    {
        int a,b,len;
        cin>>a>>b>>len;
        G[a].push_back({b,len+add[b]});
        G[b].push_back({a,len+add[a]});
        //vector存图，加上目的地点权 
    }
    dijkstra();
    cout<<dis[n]-add[n];//终点不用隔离 
}