自动搬运

查看原文

来自洛谷，原作者为

	Ybll_ 不拿蓝√不改签||泥闷的亡回来了

搬运于2025-08-24 22:26:29，当前版本为作者最后更新于2024-12-01 11:50:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

$n$ 件衣服，编号为 $1$ 到 $n$，某人想要编号为 $1$ 的那一件，对于第 $a_i$ 件衣物，你可以直接购买或者用两件指定衣物 $x_i$ 和 $y_i$ 合成，求花费的最少价值。

思路：

一眼dp，很容易就可以推出公式：

我们需要看是直接购买便宜还是合成便宜，最后直接输出 $dp_1$ 就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int id,x,y;
}a[1000005];
int n,m,dp[100005];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>dp[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].id>>a[i].x>>a[i].y;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			dp[a[j].id]=min(dp[a[j].id],dp[a[j].x]+dp[a[j].y]);
		}
	}
	cout<<dp[1];
   	return 0;
}