NOIP2012普及组复赛第4题文化之旅求本题正确的做法,解题思路以及程序.有些算法虽然能得满分但事实上是有问题的并且自己知道的就不必了.不要抄袭，请求别的更高效的做法或剪枝方法。

NOIP2012普及组复赛第4题文化之旅求本题正确的做法,解题思路以及程序.有些算法虽然能得满分但事实上是有问题的并且自己知道的就不必了.不要抄袭，请求别的更高效的做法或剪枝方法。
NOIP2012普及组复赛第4题文化之旅
求本题正确的做法,解题思路以及程序.有些算法虽然能得满分但事实上是有问题的并且自己知道的就不必了.
不要抄袭，请求别的更高效的做法或剪枝方法。

NOIP2012普及组复赛第4题文化之旅求本题正确的做法,解题思路以及程序.有些算法虽然能得满分但事实上是有问题的并且自己知道的就不必了.不要抄袭，请求别的更高效的做法或剪枝方法。
满分搜索的话,按理用下面几个剪枝就可以了.
1、最优性剪枝 （Ans < Nowdist + MinDist）
（Nowdist当前走过的路程,MinDist至少还要走多远）.
2、删去所有影响终点的城市（不可能走到的……）
3、倒搜
说实话给 PJ 组的写 STD 时是这么写的……AC过了.
虽然怎么说倒搜似乎有些说不过.
另把倒搜换成下面的剪枝也是可以过的.
设定一个X,从终点向外拓展X层.
每走一个城市看是否这X层中的任意一层被封锁.
上述的确有些郁闷,因为X取小作用不大,取大又降低了程序运行速度.
可以考虑将所有拓展层全部求出来.每2、3层跳跃一次.
100个点的图如果想卡人的话,层数不会太多的,最多10层左右.
不过后面的没有实现了.STD X 取1就可以过.
程序在学校的说……明天中午发过来>_

4文化之旅 (culture.cpp/c/pas) 【问题描述】 普及组 有一位使者要游历各国他每到一个国家都能学到一种文化但他不愿意学习任何一 种文化超过一次即如果他学习了某种文化则他就不能到达其他有这种文化的国家。不 同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同&#...

全部展开

4文化之旅 (culture.cpp/c/pas) 【问题描述】 普及组 有一位使者要游历各国他每到一个国家都能学到一种文化但他不愿意学习任何一 种文化超过一次即如果他学习了某种文化则他就不能到达其他有这种文化的国家。不 同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同有些文化会排斥外来 文化即如果他学习了某种文化则他不能到达排斥这种文化的其他国家。 现给定各个国家间的地理关系各个国家的文化每种文化对其他文化的看法以及这 位使者游历的起点和终点在起点和终点也会学习当地的文化国家间的道路距离试求 从起点到终点最少需走多少路。 【输入】 输入文件 culture.in。 第一行为五个整数 NKMST每两个整数之间用一个空格隔开依次代表国家 个数国家编号为 1 到 N文化种数文化编号为 1 到 K道路的条数以及起点和终点 的编号保证 S 不等于 T 第二行为 N 个整数每两个整数之间用一个空格隔开其中第 i 个数 Ci表示国家 i 的文化为 Ci。 接下来的 K 行每行 K 个整数每两个整数之间用一个空格隔开记第 i 行的第 j 个数 为 aijaij= 1 表示文化 i 排斥外来文化 ji 等于 j 时表示排斥相同文化的外来人aij= 0 表示 不排斥注意 i 排斥 j 并不保证 j 一定也排斥 i。 接下来的 M 行每行三个整数 uvd每两个整数之间用一个空格隔开表示国家 u 与国家 v 有一条距离为 d 的可双向通行的道路保证 u 不等于 v两个国家之间可能有多条 道路。 【输出】 输出文件名为 culture.out。 输出只有一行一个整数表示使者从起点国家到达终点国家最少需要走的距离数如 果无解则输出-1。 【输入输出样例 1】 culture.in 2 2 1 1 2 1 2 0 1 1 0 1 2 10 【输入输出样例说明】 culture.out -1 由于到国家 2 必须要经过国家 1而国家 2 的文明却排斥国家 1 的文明所以不可能到 达国家 2。 【输入输出样例 2】 culture.in 2 2 1 1 2 1 2 0 1 0 0 1 2 10 【输入输出样例说明】 路线为 1 -> 2。 【数据范围】 对于 20%的数据有 2≤N≤8K≤5 对于 30%的数据有 2≤N≤10K≤5 对于 50%的数据有 2≤N≤20K≤8 对于 70%的数据有 2≤N≤100K≤10 culture.out 10 普及组 对于 100%的数据有 2≤N≤1001≤K≤1001≤M≤N 21≤ki≤K1≤u, v≤N1≤d≤1000 S≠T1 ≤S, T≤N。

收起