本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}