首页 > 代码库 > P1796 汤姆斯的天堂梦_NOI导刊2010提高（05）
P1796 汤姆斯的天堂梦_NOI导刊2010提高（05）
题目描述
汤姆斯生活在一个等级为0的星球上。那里的环境极其恶劣，每天12小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为N的星球上天堂般的生活。
有一些航班将人从低等级的星球送上高一级的星球，有时需要向驾驶员支付一定金额的费用，有时却又可以得到一定的金钱。
汤姆斯预先知道了从0等级星球去N等级星球所有的航线和需要支付（或者可以得到）的金钱，他想寻找一条价格最低（甚至获得金钱最多）的航线。
输入输出格式
输入格式：
第一行一个正整数N(N≤100)，接下来的数据可分为N个段落每段的第一行一个整数Ki(Ki≤100)，表示等级为i的星球有Ki个。
接下来的Ki中第Tij行依次表示与等级为i，编号为i的星球相连的等级为i-l的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过1000）。
每行以0结束，每行的航线数≤100。
输出格式：
输出所需（或所得）费用。正数表示支出，负数表示收益。
输入输出样例
输入样例#1：
321 15 01 5 031 -5 2 10 01 3 02 40 021 1 2 5 3 -5 02 -19 3 -20 0
输出样例#1：
-1
说明
对于100%的数据N≤100 Ki≤100。
样例解释：
用t数组表示上一层的状态，用d数组表示本层的状态
转移方程d[i]=min(d[i],t[k]+m)
然后再把t数组替换为d数组
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 void read(int &n) 8 { 9 char c=‘+‘;int x=0;bool flag=0;10 while(c<‘0‘||c>‘9‘)11 {c=getchar();if(c==‘-‘)flag=1;}12 while(c>=‘0‘&&c<=‘9‘)13 {x=x*10+(c-48);c=getchar();}14 flag==1?n=-x:n=x;15 }16 int n,m;17 int a[10001];18 int dp[10001][31];19 int l,d[110],t[110]; 20 int main()21 {22 int i,j,k;23 read(n);24 for (i=1;i<=n;i++)25 {26 read(k);27 for (j=1;j<=k;j++)28 {29 d[j]=0x7ffff; //将d[j]初始化 30 read(l);31 while (l!=0)32 {33 read(m);34 if (d[j]>t[l]+m) d[j]=t[l]+m;35 read(l);36 }37 }38 for (j=1;j<=k;j++)39 t[j]=d[j];40 }41 int ans=1000000;42 for (i=1;i<=k;i++){43 if (ans>d[i]) ans=d[i];44 }45 printf("%d",ans);46 return 0;47 }
P1796 汤姆斯的天堂梦_NOI导刊2010提高（05）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。