璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


icpc:problems:luogup1796
problems
名称汤姆斯的天堂梦
题目编号P1796
题目链接luogu.com.cn/…
来源Luogu
算法分类动态规划, 线性动态规划
难易程度容易

汤姆斯的天堂梦

想法

读入时进行转移,使用f[i][j]记录第i层第j个的最优值。

代码实现

#include<cstdio>
 
const int N = 110;
int f[N][N], line[N], maps[N][N];
int main() {
	int n;
	scanf("%d", &n);
	for(int i=1; i<=n; i++) {
		int target, val;
		scanf("%d", &line[i]);
		for(int j=1; j<=line[i]; j++) {
			f[i][j] = 0x7f7f7f7f;
			while(true) {	
				scanf("%d", &target);
				if(target == 0)break;
				scanf("%d", &val);
				if(f[i-1][target] + val < f[i][j])
					f[i][j] = f[i-1][target] + val;
			}
		} 
	}
	int mx = f[n][1];
	for(int i=1; i<=line[n]; i++)
		if(mx > f[n][i])
			mx = f[n][i];
	printf("%d", mx);
	return 0;
} 
/app/www/public/data/pages/icpc/problems/luogup1796.txt · 最后更改: 2024/03/21 08:48 由 温婕莺