能做SEO优化的网站建设,如何修改网站后台密码,百度如何验证网站,天津和平做网站哪家好题目背景
注#xff1a;对于 k k k 短路问题#xff0c;A* 算法的最坏时间复杂度是 O ( n k log n ) O(nk \log n) O(nklogn) 的。虽然 A* 算法可以通过本题原版数据#xff0c;但可以构造数据#xff0c;使得 A* 算法在原题的数据范围内无法通过。事实上#xff0c…题目背景
注对于 k k k 短路问题A* 算法的最坏时间复杂度是 O ( n k log n ) O(nk \log n) O(nklogn) 的。虽然 A* 算法可以通过本题原版数据但可以构造数据使得 A* 算法在原题的数据范围内无法通过。事实上存在使用可持久化可并堆的算法可以做到在 O ( ( n m ) log n k log k ) O((nm) \log n k \log k) O((nm)lognklogk) 的时间复杂度解决 k k k 短路问题。详情见 OI-Wiki。
题目描述
iPig 在假期来到了传说中的魔法猪学院开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后iPig 对猪世界的世界本原有了很多的了解众所周知世界是由元素构成的元素与元素之间可以互相转换能量守恒 … \ldots …。
iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素并学会了可以转化这些元素的魔法每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪让 iPig 用最少的能量完成从一种元素转换到另一种元素 … \ldots …等等iPig 的魔法导猪可没这么笨这一次他给 iPig 带来了很多 1 1 1 号元素的样本要求 iPig 使用学习过的魔法将它们一个个转化为 N N N 号元素为了增加难度要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性因为他有坚实的后盾 … \ldots …现在的你呀
注意两个元素之间的转化可能有多种魔法转化是单向的。转化的过程中可以转化到一个元素包括开始元素多次但是一但转化到目标元素则一份样本的转化过程结束。iPig 的总能量是有限的所以最多能够转换的样本数一定是一个有限数。具体请参看样例。
输入格式
第一行三个数 N , M , E N, M, E N,M,E表示 iPig 知道的元素个数元素从 1 1 1 到 N N N 编号iPig 已经学会的魔法个数和 iPig 的总能量。
后跟 M M M 行每行三个数 s i , t i , e i s_i, t_i, e_i si,ti,ei 表示 iPig 知道一种魔法消耗 e i e_i ei 的能量将元素 s i s_i si 变换到元素 t i t_i ti。
输出格式
一行一个数表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。
样例 #1
样例输入 #1
4 6 14.9
1 2 1.5
2 1 1.5
1 3 3
2 3 1.5
3 4 1.5
1 4 1.5样例输出 #1
3提示
有意义的转换方式共 4 4 4 种 1 → 4 1\to 4 1→4消耗能量 1.5 1.5 1.5。 1 → 2 → 1 → 4 1\to 2\to 1\to 4 1→2→1→4消耗能量 4.5 4.5 4.5。 1 → 3 → 4 1\to3\to4 1→3→4消耗能量 4.5 4.5 4.5。 1 → 2 → 3 → 4 1\to2\to3\to4 1→2→3→4消耗能量 4.5 4.5 4.5。
显然最多只能完成其中的 3 3 3 种转换方式选第一种方式后三种方式仍选两个即最多可以转换 3 3 3 份样本。
如果将 E 14.9 E14.9 E14.9 改为 E 15 E15 E15则可以完成以上全部方式答案变为 4 4 4。
数据规模
占总分不小于 10 % 10\% 10% 的数据满足 N ≤ 6 , M ≤ 15 N \leq 6,M \leq 15 N≤6,M≤15。
占总分不小于 20 % 20\% 20% 的数据满足 N ≤ 100 , M ≤ 300 , E ≤ 100 N \leq 100,M \leq 300,E\leq100 N≤100,M≤300,E≤100 且 E E E 和所有的 e i e_i ei 均为整数可以直接作为整型数字读入。
所有数据满足 2 ≤ N ≤ 5000 2 \leq N \leq 5000 2≤N≤5000 1 ≤ M ≤ 200000 1 \leq M \leq 200000 1≤M≤200000 1 ≤ E ≤ 1 0 7 1 \leq E \leq 10 ^ 7 1≤E≤107 1 ≤ e i ≤ E 1 \leq ei\leq E 1≤ei≤E E E E 和所有的 e i e_i ei 为实数。
数据更新日志
2010/xx/xx原版数据2018/03/02kczno1 添加了 一组数据2018/04/20X_o_r 添加了 一组数据2021/01/08LeavingZ 添加了 两组数据。
