题目背景

改编自某题

题目描述

zzy现在决定环游中国,顺便赚点钱。zzy在一个城市最多只能赚D元,然后他可以选择退休也就是停止赚钱,或者去其它城市工作。当然,他可以在别处工作一阵子后又回到原来的城市再赚D元。这样的往返次数是没有任何限制的。

城市间有P条单向路径连接,共有C座城市,编号从1到C。路径i从城市Ai到城市Bi,在路径行走上不用任何花费。

zzy还可以乘飞机从某个城市飞到另一个城市。共有F条单向的航线,第i条航线是从城市Ji飞到另一座城市Ki,费用是Ti元。假如zzy身上没有现钱,他可以用以后赚的钱来付机票钱。

zzy可以从任何一个城市出发开始赚钱,并且选择在任何时候、任何城市退休。现在zzy想要知道,如果在工作时间上不做限制,那么zzy共可以赚多少钱呢?如果赚的钱也不会出现限制,那么就输出orz。

有环的话就是orz了,,然后就是取相反数,跑spfa,就有最长路了。。

输入格式

第一行,4个用空格分开的正整数,D,P,C,F。

第二行到P+1行,第i+1行包含2个用空格分开的整数,表示一条从城市Ai到城市Bi的单向路径。

接下来的F行,每行3个用空格分开的正整数,表示一条从城市Ji到城市Ki的单向航线,费用为Ti。

输出格式

如果zzy赚的钱没有限制,输出orz。如果有限制,那么就输出在给定的规则下zzy最多可以赚到的钱数。

输入输出样例

输入 #1

输出 #1

说明/提示

对于100%的数据,1<=D<=1000,1<=P<=200,2<=C<=300,1<=F<=400。

最后修改日期:2020年1月10日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。