[ABC340D] Super Takahashi Bros. 题解

LANDER_TT · 2024-11-28 08:52:43 · 题解

一、思路

观察数据范围，发现 2\leq N\leq2\times10^5，无法使用dfs暴力求解

考虑建图后使用Dijkstra算法求解

题目要求连接相邻的两个关卡，所以可能出现重边的情况，在存储边时，仅保留最短的边

接下来在跑一遍迪杰斯特拉就可以了

二、代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
    int u,v,w;
}e[500005];
int tot,n,h[500005],d[500005],vs[500005];
void add(int u,int v,int w){
    e[++tot]={v,h[u],min(w,e[tot].w)};//存边时存最小的边
    h[u]=tot;
}
priority_queue<pair<int,int> > q;
void dj(int st){//迪杰斯特拉
    for(int i=1;i<=n;++i)d[i]=1e18;
    d[st]=0;
    q.push({0,st});
    while(!q.empty()){
        pair<int,int> now=q.top();
        q.pop();
        int u=now.second;
        if(vs[u])continue;
        vs[u]=1;
        for(int i=h[u];i;i=e[i].v){
            int v=e[i].u,w=e[i].w;
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                q.push({-d[v],v});
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=2*n+5;++i)e[i].w=1e18;//初始化权值
    for(int i=1,a,b,x;i<n;++i){
        cin>>a>>b>>x;
        add(i,i+1,a);//按照题目要求建边
        add(i,x,b);
    }
    dj(1);
    cout<<d[n];
    return 0;
}