首页 > 代码库 > 【HDOJ】2851 Lode Runner
【HDOJ】2851 Lode Runner
开始没理解题意。原来destinations是指路的序号。而不是点。DP。
1 #include <stdio.h> 2 #include <string.h> 3 4 int dp[2005]; 5 6 typedef struct { 7 int s, e, w; 8 } road_st; 9 10 road_st roads[2005]; 11 12 int main() { 13 int case_n; 14 int n, m, des; 15 int i, j, min; 16 17 scanf("%d", &case_n); 18 19 while (case_n--) { 20 scanf("%d%d", &n, &m); 21 for (i=1; i<=n; ++i) 22 scanf("%d%d%d", &roads[i].s, &roads[i].e, &roads[i].w); 23 memset(dp, 0, sizeof(dp)); 24 dp[1] = roads[1].w; 25 for (i=2; i<=n; ++i) { 26 min = 0x7fffffff; 27 for (j=1; j<i; ++j) { 28 if (roads[i].s <= roads[j].e && dp[j]!=-1 && dp[j]<min) 29 min = dp[j]; 30 } 31 if (min < 0x7fffffff) 32 dp[i] = min + roads[i].w; 33 else 34 dp[i] = -1; 35 } 36 for (i=0; i<m; ++i) { 37 scanf("%d", &des); 38 printf("%d\n", dp[des]); 39 } 40 } 41 42 return 0; 43 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。