P1171: 挂机留真爱♂

评测方式:Normal  时空限制:1.000s/128MB

题目描述

NOKK要从百度网盘上取回大小为N MB的游戏大作《上古卷轴》,但是百度网盘甩给了他56KB/s的速度。于是,他想出了一个办法:控制许多台别人家的电脑同时下载,再同时向自己的电脑传输数据。
100台电脑间通过M条网线相互连接,且网线是有向的;且每条有向线路都有上限带宽ci,单位为MB每秒; 
规定编号为1的是百度网盘,编号为D是NOKK的电脑。
同时NOKK不希望挂机下载时间太久,因为这会降低他最爱的HDD硬盘的寿命,他希望在P秒内下载完毕;
如果能在P秒时间下载完成,输出"YES",否则输出"NO"。

输入格式

第1行:一个正整数T,表示数据组数;
第2行:4个整数 N,M,D,P。
接下来M行: 每行有三个整数:x,y,c。表示一条从电脑x连向电脑y的有向网线,带宽为c。

输出格式

对于每组数据,如果能在P秒时间下载完成,输出"YES",否则输出"NO"。 

样例输入

1
200 5 4 4
3 4 10
2 4 20
2 3 30
1 2 40
1 4 20

样例输出

YES

提示

本题为真·签到题
1<=T<=10,2<=N<=19260817,0<=M<=20001<=D<=100,0<=c<=1000000,0<=P<=13
可能出现某台电脑没有网线与其相连
并没有子任务

来源

2019暑期校内集训-ZTJ 网络流