首页 > 代码库 > 救命（洛谷 U4525）
救命（洛谷 U4525）
题目背景
XS中学的校长积劳成疾，最终由于无聊而卧病在沙发。需要药（pi）水（gu）拯救他的生活。
题目描述
现在有n种药水，编号分别为1..n，能拯救校长的药水编号为n
每个药水都可以购买到，但有的价格很便宜，有的很贵。
你还知道m种神奇的合成方法，可以将某些不同的药水合成成为一个新的药水。
现在，你需要求出合成出n号药水所需要花费的最小金钱，以及在保证花费最小情况下的最少需要合成的次数。
输入输出格式
输入格式：
第一行两个数n,m
接下来n行，每行有一个数a[i]，表示i号药水的价格。
接下来m行，每行描述一个合成方法。
对于每个合成方法：第一个数x表示所需要的药水的个数。接下来x个数，分别表示所需要的每个药水的编号，最后一个数表示这x个药水所合成的药水的编号
输出格式：
仅两个数，分别表示最小花费和满足该花费的最小合成次数，中间用空格隔开。
输入输出样例
输入样例#1：
10 412310042221001003 1 2 3 42 4 5 102 6 7 92 9 8 4
输出样例#1：
10 2
说明
n<=1000
m<=10000
2<=x<=10
Tips:看标签！！！
/* 对于每种药，统计一个mon代表最小花费，step代表在mon基础上的最小步数， 不断用能合成i这种药的Σmon[j] 来更新mon[i]，共更新n次就可以，最后求 mon[n]。*/#include<cstdio>#include<iostream>#define N 1010#define M 10010using namespace std;int mon[N],step[N],n,m;struct node{ int tot,s[11],t;};node a[M];int read(){ char c=getchar();int num=0,flag=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)flag=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*flag;}int main(){ n=read();m=read(); for(int i=1;i<=n;i++) mon[i]=read(); for(int i=1;i<=m;i++) { a[i].tot=read(); for(int j=1;j<=a[i].tot;j++) a[i].s[j]=read(); a[i].t=read(); } for(int t=1;t<=n;t++) { int flag=0; for(int i=1;i<=m;i++) { int sum=0,maxn=0; for(int j=1;j<=a[i].tot;j++) sum+=mon[a[i].s[j]],maxn+=step[a[i].s[j]]; if(sum<mon[a[i].t]) { step[a[i].t]=maxn+1; mon[a[i].t]=sum; flag=1; } if(sum==mon[a[i].t]&&maxn+1<step[a[i].t]) step[a[i].t]==maxn+1,flag=1; } if(!flag)break; } printf("%d %d",mon[n],step[n]); return 0;}
救命（洛谷 U4525）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。