【题目描述】
平面上有n个点（n≤100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
【输入描述】
共n+m+3行，其中:
第一行为整数n。
第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。
第n+2行为一个整数m，表示图中连线的个数。
此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。
最后一行：两个整数s和t，分别表示源点和目标点。
【输出描述】
一行，一个实数（保留两位小数），表示从s到t的最短路径长度。
【样例输入】
5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5
【样例输出】
3.41
【题目描述】
小T和小K都是OIER，入选省队后有幸去苏州参加JSOI集训，训练之余，他们相约一起去苏州乐园玩。
苏州乐园里有一个非常热门的游乐项目叫双人滑翔翼。小T想和小K一起乘双人滑翔翼，但是排在他们前面的一大群人却为了搭配问题而争执不休，小T和小K便自告奋勇上前为他(她)们排扰解难。
排在小T和小K前面的一大群人中有N个男人和N个女人。本着“男女搭配，干活不累”的原则，他(她)们希望一男一女结成对子飞上天去。由于双人滑翔翼飞行的稳定性很大程度上决定于两侧是否平衡，所以两个人体重相差越小则组成的搭档也越好。
现在已知每个人的体重，你的任务就是将所有人结成N对并使各对的体重差的总和最小。一对的体重差定义为重的减轻的的值，此值一定大于等于0，譬如有一对人，男的体重为50，女的体重为55，则他(她)们的体重差为5，反过来如果男的体重为55，女的体重为50，则他(她)们的体重差仍然是5。
【输入描述】
第一行包含一个自然数N（1≤N≤1000），表示有N对人；
第2～N+1行：每行包含一个自然数，表示N个男人的体重；
第N+2～2N+1行：每行包含一个自然数，表示N个女人的体重。
【输出描述】
仅有一行包含一个整数，表示配对后N对男女的体重差的总和的最小值。
【样例输入】
4 2 8 5 5 1 4 10 7
【样例输出】
6
一、什么是剪枝
首先应当明确的是，“剪枝”的含义是什么。我们知道，搜索的进程可以看作是从树根出发，遍历一棵倒置的树——搜索树的过程。而所谓剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是坚强搜索树中的某些“枝条”，故称剪枝。
我们在编写搜索程序的时候，一般都要考虑剪枝。显而易见，应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留。设计好的剪枝判断方法，往往能够使程序的运行时间大大缩短；否则，可能适得其反。
二、剪枝的原则
1.正确性：
我们知道，剪枝方法之所以能够优化程序的执行效率，正如前文所述，是因为它能够“剪去”搜索树中的一些“枝条”。然而，如果在剪枝的时候，将“长有”我们所需要的解的枝条也剪掉了，那么，一切优化也就失去了意义。所以，对剪枝的第一个要求就是正确性，即必须保证不丢失正确的结果，这是剪枝优化的前提。
2.准确性：
在保证正确性的基础上 ，对剪枝判断的第二个要求就是准确性，即能够尽可能多地剪去不能通向正确的枝条。剪枝方法只有在具有了较高的准确性的时候，才能真正收到优化的效果。
3.高效性：
一般来说，设计好剪枝判断方法之后，我们对搜索树的每个枝条都要执行一次判断操作。然而，由于是利用出解的“必要条件”进行判断，所以，必然是有很多不含正解的枝条没有被剪枝。这些情况下的剪枝判断操作，对于程序的
效率提高无疑是具有副作用的。为了尽量减少剪枝判断的副作用，我们除了要下功夫改善判断的准确性之外，经常还需要提高判断操作本身的时间效率。
然而这就带来了一个矛盾：我们为了加强优化效果，就必须提高剪枝判断的准确性，因此，常常不得不提高判断操作的复杂度，也就同时降低了剪枝判断的时间效率；但是，如果剪枝判断的时间消耗过多，就有可能降低、甚至完全抵消
提高判断准确性所能带来的优化效果，这恐怕会得不偿失。很多情况下，能否较好地解决这个矛盾，往往成为搜索算法优化的关键。
综上所述:我们可以把剪枝优化的主要原则归结为六个字：正确、准确、高效。
三、深度优先搜索的优化技巧
1.优化搜索顺序
在一些搜索问题中，搜索树的各个层次、各个分支之间的顺序不是固定的。不同的搜索顺序会产生不同的搜索树形态，其规模大小也相差甚远。
2.排除等效冗余
在搜索过程中，如果我们能够判断从搜索树的当前节点上沿着某几条不同分支到达的子树是等效的，那么只需要对其中的一条分支执行搜索。
3.可行性剪枝
在搜索过程中，及时对当前状态进行检查，如果发现分支已经无法到达递归边界就及时回溯。这就好比我们在道路上行走时，远远看到前方是一个死胡同，就应该立即折返，走到路的尽头再返回。
某些题目条件的范围限制是一个区间，此时可行性剪枝也被称为上下界。
4.最优性剪枝
在最优化问题的搜索过程中，如果当前花费的代价已经超过当前搜到的最优解，那么取多么优秀的策略到达递归边接，都不可能更新答案，此时可以停止对当前分支的搜索回溯。
5.记忆化
可以记录每个状态的搜索结果，在重复遍历一个状态时直接搜索并返回。这好比我们进行深度优先遍历时，标记一个节点是否已经被访问过。
四、例题
【问题描述】
将整数n分成k份，且每份不能为空，问有多少种不同的分法？当n=7，k=3时，下面三种分法是被认为是相同的：1，1，5；
1，5，1；5，1，1。
【输入格式】
输入文件只有一行，为两个整数n和k。（6<n<=200， 2<=k<=6）
【输出格式】
输出文件仅有一行，为一个整数，即不同的分法数。
【样例输入】
7 3
【样例输出】
4
【样例解释】
四种分法为：1，1，5；1，2，4；1，3，3；2，2，3；
【数据规模】
对100%的数据，6<=n<=200, 2<=k<=6
【题目描述】
给定一个N个数的数组，M次操作，每次操作为下列操作之一。求最后的数组。
操作1：在第X个数之后插入一个数Y。
操作2：删除第X个数。
操作3：对区间[X，Y]进行排序。
操作4：对区间[X，Y]进行翻转。
操作5：删除区间[X，Y]中值为Z的数。
【输入描述】
第一行两个整数N，M（N，M≤100000）含义见试题描述。
第二行N个整数，表示原来的数组。
接下来M行，每行第一个数OPT，表示操作类型。
对于操作1，接下来两个数X，Y，含义见题面描述，保证0≤X≤当前数的个数，若X=0，表示在数组开头插入。
对于操作2，接下来一个数X，含义见题面描述，保证1≤X≤当前数的个数。
对于操作3，接下来两个数X，Y，含义见题面描述，保证1≤X≤Y≤当前数的个数，保证操作3不超过10个。
对于操作4，接下来两个数X，Y，含义见题面描述，保证1≤X≤Y≤当前数的个数，保证操作4不超过10个。
对于操作5，接下来三个数X，Y，Z，含义见题面描述，保证1≤X≤Y≤当前数的个数，保证操作5不超过10个。
【输出描述】
输出若干个数，表示最后的数组。
【样例输入】
5 5 1 4 3 2 5 3 2 4 4 4 5 5 2 3 2 5 2 3 1 1 0 9
【样例输出】
9 1 3 5 4