2014
11-27

# Pair

There are n cities in country X. Some pairs of cities are connected by bidirectional roads, and there exists one and only one path between every pair of cities.
Lily wants to take a trip in country X. She can start from any city, and she wouldn’t visit a city twice. Lily is effeminate, so the total distance of this trip should not be larger than L.
Your task is to calculate the number of all possible trips. Two trips are distinct if and only if the set of cities they contain are different.

The first line contains two integers n and m, n is the number of cities, and m is the number of roads. The following m lines describe m roads, each of which contains three integers a, b, c, representing that a and b are connected by an undirected road which length is c. The last line contains a integer L.
1<=n<=100000, 1<=c<=10000, 1<=L<=1000000000.

The first line contains two integers n and m, n is the number of cities, and m is the number of roads. The following m lines describe m roads, each of which contains three integers a, b, c, representing that a and b are connected by an undirected road which length is c. The last line contains a integer L.
1<=n<=100000, 1<=c<=10000, 1<=L<=1000000000.

3 2
2 3 10
1 3 10
15
4 3
2 3 10
1 3 5
3 4 3
14

5
9

1. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。

2. “再把所有不和该节点相邻的节点着相同的颜色”，程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

3. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

4. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。