问题 23839 --layout

23839: layout

时间限制: 1 Sec  内存限制: 128 MB
提交: 91  解决: 33
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][472kb]

题目描述

    和人类一样,奶牛们在打饭的时候喜欢和朋友站得很近。
    约翰的编号为1到n的n(2<=n<=1000)只奶牛正打算排队打饭。现在请你来安排她们,让她们在数轴上排好队。奶牛的弹性很好,同一个坐标可以站无限只奶牛,排队的顺序必须和她们编号的顺序一致。有M对奶牛互相爱慕,她们之间的距离不能超过一定的值,有K对奶牛互相敌视,她们的距离不能小于一定的值。
    那么,首尾奶牛的最大距离是多少呢?

输入

第一行输入n,M,K,接下来M行每行三个整数x,y,z,表示编号为x和y的两头奶牛之间的距离最大不超过z,再接下来K行每行三个整数a,b,c,表示编号为a和b的两头奶牛之间的距离最少为c。

输出

如果没有合理方案,输出-1,如果首尾两头牛的距离可以无限大,输出-2,否则输出一个整数表示首尾奶牛的最大距离。

样例输入

4 2 1
1 3 10
2 4 20
2 3 3

样例输出

27

提示

样例说明:

四只牛分别在0,7,10,27。

来源

[提交][状态]