题解：P7082 [NWRRC2013] Dwarf Tower
Ybll_
·
·
题解
题意：
# 思路：
一眼**dp**，很容易就可以推出公式：
$$dp_{a_i}=\min(dp_{a_i},x_i+y_i)$$
我们需要看是直接购买便宜还是合成便宜，最后直接输出 $dp_1$ 就可以了。
# 代码：
```cpp
#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;
}
```