ABC340D 题解

KSCD_ · 2024-02-10 21:46:32 · 题解

题意

游戏有 n 个阶段，对于第 i 个阶段，可以消耗 A_i 秒开启第 (i+1) 个阶段，也可以消耗 B_i 秒开启第 x_i 个阶段。初始只能进行第 1 个阶段，求开启第 n 个阶段需要的最短时间。

思路

本题考查图论建模和最短路。

由于 A_i 和 B_i 描述的都是阶段之间转移的代价，容易想到以阶段为点，阶段转移为边，所需时间为边权建图，则所求最短时间即为点 1 到点 n 的最短路。

则对于前 (n-1) 个点中的点 i ，均向点 (i+1) 连一条边权为 A_i 的有向边，向点 X_i 连一条边权为 B_i 的有向边。

之后用最短路算法跑单源最短路即可，Dijkstra算法可过。

代码

#include<iostream>
#include<vector>
#include<queue>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=2e5+10;
const int maxs=1e15;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; if(ch==EOF) return 0; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int n;
struct edg
{
    int v,w;
};
vector <edg> edge[N];//邻接表存边 
void add(int u,int v,int w)
{
    edg t;
    t.v=v;
    t.w=w;
    edge[u].push_back(t);
}//加有向边 
int s[N];//最短路长度 
bool v[N];//是否已经计算完最短路 
priority_queue <pii > q;//注意为大根堆，且按pair的first排序 
signed main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int a=read(),b=read(),x=read(); 
        add(i,i+1,a);
        add(i,x,b);//加边 
    } 
    for(int i=1;i<=n;i++)
        s[i]=maxs,v[i]=0;
    s[1]=0;
    q.push({0,1});//Dijkstra初始化 
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(v[u])
            continue;
        v[u]=1;
        for(int i=0;i<edge[u].size();i++)
        {
            int ne=edge[u][i].v,tw=edge[u][i].w;
            if(s[ne]>s[u]+tw)
            {
                s[ne]=s[u]+tw;
                if(!v[ne])
                    q.push({-s[ne],ne});//取负，把大根堆用作小根堆 
            }
        }
    }//Dijkstra
    cout<<s[n];
    return 0;
}