2014
02-17

# Lode Runner

Lode Runner is a famous game, I think you played in your childhood.

Ok, now, I simple the problem. In the game, it has N horizontal roads, the ladders always stay at right side vertically, and the ladders are extending towards up and down with unlimited length. If ladder near or cross a road, little WisKey will walk on the road by climbed the ladder. Two roads were covered by each other in the X-axis; it will be considered can be passing through. Each road has an integer W means the dangerous level.

Little WisKey must start at No.1 road, and he can’t go back, he always go ahead. WisKey want to go some roads, so he needs to know how minimum sum of dangerous will happen. You can finish the game, yes?

The first integer C represents the number of cases, And C cases followed.

Each test case contains a single integer N roads (1<=N<= 2000) and M destinations (1<=M<=500). The next N line contains three integers Si, Ei, Wi, meaning the road build from Si to Ei, and the Wi dangerous level (0 <= Si <= Ei <= 1000, 1 <= Wi <= 1000). And the roads sorted by Ei increasing yet. The last M line contains integers mean little WisKey’s destinations.

The first integer C represents the number of cases, And C cases followed.

Each test case contains a single integer N roads (1<=N<= 2000) and M destinations (1<=M<=500). The next N line contains three integers Si, Ei, Wi, meaning the road build from Si to Ei, and the Wi dangerous level (0 <= Si <= Ei <= 1000, 1 <= Wi <= 1000). And the roads sorted by Ei increasing yet. The last M line contains integers mean little WisKey’s destinations.

3
10 4
1 4 7
5 6 3
3 7 5
2 9 8
10 13 8
12 14 11
11 15 13
16 18 5
17 19 6
8 20 9
1
2
3
10
5 5
1 4 5
3 6 10
5 8 20
2 9 1
7 10 2
1
2
3
4
5
4 4
1 5 1
2 7 20
2 7 3
7 9 4
1
2
3
4 

7
-1
12
24
5
15
35
6
8
1
21
4
8

#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <cstring>
#include <string>

using namespace std;
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define ll long long
#define eps 1e-9
#define N 2100

ll dis[N];
struct Node
{
int l,r,d;
}node[N];

int main()
{
int t,n,m,a;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].d);
memset(dis,-1,sizeof(dis));

dis[1] = node[1].d;
for(int i=1;i<=n;i++)
{
if(dis[i]==-1) continue;
for(int j=i+1;j<=n;j++)
if(node[j].l<=node[i].r)
if(dis[j]==-1||dis[j]>dis[i]+node[j].d)
dis[j] = dis[i]+node[j].d;
}

for(int i=0;i<m;i++)
{
scanf("%d",&a);
printf("%I64d\n",dis[a]);
}

}
}

1. “可以发现,树将是满二叉树,”这句话不对吧，构造的树应该是“完全二叉树”，而非“满二叉树”。

2. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧

3. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。