BZOJ 1726: [Usaco2006 Nov]Roadblocks第二短路（次短路）

Input

* 第1行: 两个整数，N和R，用空格隔开

* 第2..R+1行: 每行包含三个用空格隔开的整数A、B和D，表示存在一条长度为 D(1 <= D <= 5000)的路连接农场A和农场B

Output

* 第1行: 输出一个整数，即从农场1到农场N的第二短路的长度

4 4
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output

450

1.如果dis1[next]>dis1[now]+len，那么dis1肯定要被更新。dis2[next]也要被更新，和原来的dis1[next]相比较。
2.如果dis1[next]<dis1[now]+len，如果dis2[next]>dis1[now]+len，那么更新次短路，也就是说从now可以松弛一条次短路出来。
3.如果dis1[next]=dis1[now]+len，那么也就是说从now松弛到next也是可以的，但是不会改变最短路。但是如果能更新此段路的话那么就得从Now松弛了。

hdu 5884 Sort（二分+K叉哈夫曼树）

Problem Description
Recently, Bob has just learnt a naive sorting algorithm: merge sort. Now, Bob receives a task from Alice.
Alice will give Bob N sorted sequences, and the i-th sequence includes ai elements. Bob need to merge all of these sequences. He can write a program, which can merge no more than k sequences in one time. The cost of a merging operation is the sum of the length of these sequences. Unfortunately, Alice allows this program to use no more than T cost. So Bob wants to know the smallest k to make the program complete in time.

Input
The first line of input contains an integer t0, the number of test cases. t0 test cases follow.
For each test case, the first line consists two integers N (2N100000) and T (Ni=1ai<T<231).
In the next line there are N integers a1,a2,a3,...,aN(i,0ai1000).

Output
For each test cases, output the smallest k.

Sample Input
1
5 25
1 2 3 4 5
Sample Output
3

#1
Input: 1 100
Output: 49

#2
Input: 2 100
Output: 74

N <= 10^18