#P1546. uva4409 - Ironman Race in Treeland

    ID: 562 传统题 1000ms 512MiB 尝试: 169 已通过: 41 难度: 7 上传者: 标签>CF2200提高+/省选-点分治树状数组离散化二分查找可行性剪枝

uva4409 - Ironman Race in Treeland

题目描述

河蟹国的道路特别有特点,每一条道路上都有许多景点供游客观赏,同时每条路要经过都要付一定的钱。而河蟹国的特点就是任意两个城市之间有切仅有一条简单路径,这样使游客旅行方便了许多。 XL 准备在河蟹市进行一次旅行,他可以从任意一个城市出发,经过不重复的一些路径之后结束他的旅程。但是他带的钱有限,所以他希望知道在最好情况下自己最多能够得到多少欢乐值。 当然,这个欢乐值可能为 00 ——没有任何一个他喜欢并且可以去的景点,所以他就世界回家看仙剑 3 去了。

输入格式

第一行三个整数 NN, MM, KK,分别表示河蟹国的城市数,道路数和 XL 身上所带的钱的数量。 

接着有 MM 行,每行 44 个整数 AiA_i, BiB_i, COSTiCOST_i, VALiVAL_i,分别表示第 i−1i-1 条路径连接着 AiA_i,BiB_i 两个城市,经过它需要付 COSTiCOST_i 元钱并且得到 VALiVAL_i 的欢乐值。

输出格式

输出文件仅一行一个整数,表示XL在最好的情况下能够得到的欢乐值是多少。

样例输入

4 3 2
1 2 1 1
1 3 1 2
1 4 2 3

样例输出

3

数据规模及约定

1≤N≤3×1041\le N\le 3\times 10^4,1≤M≤9×1081\le M\le 9\times 10^8,1≤K≤1091\le K\le 10^9;

0≤COSTi≤1030\le COSTi\le 10^3,0≤VALi≤1030\le VALi\le 10^3。

题目来源

鸣谢刘汝佳先生授权使用 (BZOJ)

ACM/ICPC 2008 吉隆坡赛区