题目名称	811. 交换
输入输出	`swap.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	Makazeu 于2012-06-14加入
开放分组	全部用户
提交状态
分类标签	动态规划图论最短路
	分享题解

通过：17，提交：52，通过率：32.69%
Sky_miner	100	0.002 s	0.29 MiB	C++
xxcxcxcx	100	0.002 s	0.31 MiB	C++
xxcxcxcx	100	0.002 s	0.32 MiB	C++
liu_runda	100	0.003 s	0.38 MiB	C++
dishierweidu	100	0.003 s	0.38 MiB	C++
ユッキー	100	0.003 s	0.56 MiB	C++
乐	100	0.004 s	0.43 MiB	C++
Truth.Cirno	100	0.004 s	3.24 MiB	C++
Sky_miner	100	0.005 s	0.26 MiB	C++
Mine_pass	100	0.005 s	0.35 MiB	C++

关于交换的近10条评论(全部评论)
n次SFPA，每次把起点的等级记录下来每找一条边判断等级差，符合的话再更新交换途中遇到的等级最大值与最小值。还有数据范围好小哇哇哇ユッキー 2017-11-09 18:26 6楼
SPFA大法好好好 liu_runda 2015-12-01 10:35 5楼
有一个似乎像是判环的东西加上就对了，还是数据弱？ /deal with loop/ if (costnow>cost[1]) return; Truth.Cirno 2012-10-22 08:57 4楼
Orz Truth.Cirno 2012-10-21 14:42 3楼
我一开始写的DP，没有处理环，70分。。。。后来经wyfenger的指教，改用SPFA、AC。。。。 Makazeu 2012-10-21 14:39 2楼
不会解决环 Truth.Cirno 2012-10-21 14:27 1楼

811. 交换

★ 输入文件：swap.in 输出文件：swap.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】
为了报答嘟嘟消灭病毒之举，微生物之王小A 准备把景天得魔剑赠送给他。但是小A又不想白白的给他，准备让他用100000 个金币来换（ps：这还是送？）。嘟嘟初来乍到，哪里拿得出这么多金币，但有的确想要到魔剑，便请求小A 降低点价格。小A 说：“嗯，如果你能替我拿到龙王的龙鳞，我可以只要90000；如果你能替我拿到龙王的龙角，我可以只要50000 金币。”嘟嘟就跑到龙王那里，向他要龙鳞或龙角，龙王要他用金币换，或者替他拿到其他的东西，他就可以降低价格。嘟嘟于是又跑到了其他地方，其他人也提出了差不多得要求，要么直接用金币交换，要么找到他们想要的东西换得较低的价格。不过嘟嘟不必要用多样的东西换一样东西，因为不会获得更低得交换价格。
嘟嘟这下犯了难，但他又非常想得到魔剑。所以他只好想你求助，让他用最少的钱换到魔剑。
另外还要说的是，微生物王国的一些人们相互间都多少有点矛盾且每个人有个等级，每两个人间可能互相都有厌恶值（这个两个人互相的厌恶值相等，其中厌恶值等于两人的等级差）。所以厌恶值超过一定限制的两个人不会进行任何形式的交换。但是嘟嘟救助了这个世界，他们是都会同意和你交换的。但是如果你和某个人进行了交换，那么厌恶他的人就不会再和你交换了，因为他们认为这样是间接地和对方交换。因此你要考虑所有的情况以后给他提供一个最好的方案。为了方便起见，我们把所有要交换的物品从1 到n 进行编号。魔剑也看做一个物品，且编号总是1。每件物品都要有一个对应的价格p，所属的主人的等级为L，以及一系列的交换物Ti 和该交换物所对应可以给的较低价格Vi。如果两个人的厌恶值超过了M，就不能进行“间接交易”。你必须根据给出的数据来计算出嘟嘟最少需要多少金币才能获得魔剑
【输入数据】
输入第一行是两个整数M，N，依次表示厌恶值差距限制和物品的总数。接下来按照编号从小到大依次给出了N 个物品的描述。每个物品的描述开头是三个非负整数P、L、X（X< N），依次表示该物品的价格、其拥有者的等级和替代品总数。接下来X 行每行包括两个整数T 和V，分别表示替代品的编号和可以降低到的价格。
【输出数据】
输出最少需要的金币数。
【样例输入】
1 4
10000 3 1
3 5000
1000 2 1
4 2000
3000 2 2
2 2000
4 100
50 2 0
【样例输出】
5150
【数据范围】
对于50 的测试数据，1<=N<=5
对于100% 的测试数据，1 <= N <= 100