在杨辉三角形中，第n行（从0开始计数，即第n+1 行有n+1个数）的所有数字之和等于2^n。

A．正确	B．错误

猫和老鼠

时间限制：1.0 s

内存限制：512.0 MB

题目描述

猫和老鼠所在的庄园可以视为一张由n个点和m条带权无向边构成的连通图。结点依次以1,2,...,n编号，结点i（1≤i≤n）有价值为ci的奶酪。在m条带权无向边中，第i（1≤i≤m）条无向边连接结点ui与结点vi，边权wi表示猫和老鼠通过这条边所需的时间。

猫窝位于结点a，老鼠洞位于结点b。对于老鼠而言，结点u是安全的当且仅当：

老鼠能规划一条从结点u出发逃往老鼠洞的路径，使得对于路径上任意结点x（包括结点u与老鼠洞）都有：

猫从猫窝出发到结点x的最短时间严格大于老鼠从结点u沿这条路径前往结点x所需的时间。

老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能，但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失，老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。

输入格式

第一行，两个正整数n,m，分别表示图的结点数与边数。

第二行，两个正整数a,b，分别表示猫窝的结点编号，以及老鼠洞的结点编号。

第三行，n个正整数c1,c2,...,cn，表示各个结点的奶酪价值。

接下来 行中的第i行（1≤x≤m）包含三个正整数ui,vi,wi，表示图中连接结点ui与结点vi的边，边权为wi。

输出格式

输出一行，一个整数，表示老鼠所能拿到的奶酪价值之和。

输入样例 1

5 5
1 2
1 2 4 8 16
1 2 4
2 3 3
3 4 1
2 5 2
3 1 8

输出样例 1

22

输入样例 2

6 10
3 4
1 1 1 1 1 1
1 2 6
2 3 3
3 1 4
3 4 5
4 5 8
5 6 2
6 4 1
3 2 4
5 4 4
3 3 6

输出样例 2

3

数据范围

对于40的测试点，保证1≤n≤500，1≤m≤500。

对于所有测试点，保证1≤n≤105，1≤m≤105，1≤a,b≤n且a≠b，1≤ui,vi≤n，1≤wi≤109。

宝石项链

时间限制：1.0 s

内存限制：512.0 MB

题目描述

小 A 有一串包含n枚宝石的宝石项链，这些宝石按照在项链中的顺序依次以1,2,...,n编号，第n枚宝石与第1枚宝石相邻。项链由m种宝石组成，其中第i枚宝石种类为ti。

小 A 想将宝石项链分给他的好朋友们。具体而言，小 A 会将项链划分为若干连续段，并且需要保证每段都包含全部种宝石。请帮小 A 计算在满足条件的前提下，宝石项链最多可以划分为多少段。

输入格式

第一行，两个正整数n,m，分别表示宝石项链中的宝石的数量与种类数。

第二行，n个正整数ti,t2,...,tn，表示每枚宝石的种类。

输出格式

输出一行，一个整数，表示宝石项链最多可以划分的段数。

输入样例 1

6 2
1 2 1 2 1 2

输出样例 1

3

输入样例 2

7 3
3 1 3 1 2 1 2

输出样例 2

2

数据范围

使用 math.h 或 cmath 头文件中的函数，表达式 sqrt(4) 的结果类型为 double 。

A．正确	B．错误

快速排序在最坏情况下的时间复杂度为O(n log n)，可以通过随机化选择基准值（pivot）的方法完全避免退化。

A．正确	B．错误