即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

1262: 魔法宝石 (“玲珑杯”河南工业大学ACM程序设计大赛)

编程语言 su20145104009 10℃ 0评论
本文目录
[隐藏]

1.问题 C: 魔法宝石

时间限制: 2 秒  内存限制: 64 MB


提交: 242  解决: 46


提交 状态 

1.1.1.题目描述

小s想要创造n种魔法宝石。小s可以用ai的魔力值创造一棵第i种魔法宝石,或是使用两个宝石合成另一种宝石(不消耗魔力值)。请你帮小s算出合成某种宝石的所需的最小花费。

1.1.2.输入

第一行为数据组数T(1≤T≤3)。


对于每组数据,首先一行为n,m(1≤n,m≤10^5)。分别表示魔法宝石种类数和合成魔法的数量。


之后一行n个数表示a1到an。(1≤ai≤10^9)。a_i表示合成第i种宝石所需的魔力值。


之后n行,每行三个数a,b,c(1≤a,b,cn),表示一个第a种宝石和第b种宝石,可以合成一个第c种宝石。

1.1.3.输出

每组数据输出一行n个数,其中第i个数表示合成第i种宝石的魔力值最小花费。

1.1.4.样例输入

1
3 1
1 1 10
1 2 3


1.1.5.样例输出

1 1 2

提示

思路应该是很简单的。

就是更新宝石的魔力值。

每当我们使用两个宝石合成了宝石花费的魔力小于原本的魔力,那么就把所有和这个合成的宝石有关的其它宝石也进行更新~深搜即可

#include 
#include 
#include 
using namespace std;
struct node
{
 int x,y,z;
}h[100005];
vectorlink[100005];
long long a[100005];
node temp;
//深搜查找和z宝石相关的其它宝石 并进行更新 
void dfs(int z)
{
 for(int j=0;ja[temp.x]+a[temp.y])
  {
   a[temp.z]=a[temp.x]+a[temp.y];
   dfs(temp.z);
  }
 }
}
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n,m;
  memset(link,0,sizeof(link));
  memset(h,0,sizeof(h));
  memset(a,0,sizeof(a));
  scanf("%d %d",&n,&m);
  for(int i=1;i<=n;i++)
  scanf("%lld",&a[i]);
  int x,y,z;
 
  for(int i=0;ia[x]+a[y])
   {
    a[z]=a[x]+a[y];
    dfs(z);
   }
  }
  printf("%lld",a[1]);
  for(int i=2;i<=n;i++)
  {
   printf(" %lld",a[i]);
  }
  printf("\n");
 }
 return 0;
} 










转载请注明:CodingBlog » 1262: 魔法宝石 (“玲珑杯”河南工业大学ACM程序设计大赛)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情