【HDOJ】2851 Lode Runner

 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 }