【NOIP模拟赛】排队

2014年11月5日1,9220

【问题描述】

Czy喜欢将他的妹子们排成一队。假设他拥有N只妹纸,编号为1至N。Czy让他们站成一行,等待自己来派送营养餐。这些妹纸按照编号大小排列,并且由于它们都很想早点吃饭,于是就很可能出现多只妹纸挤在同一位置的情况(也就是说,如果我们认为妹纸位于数轴上,那么多只妹纸的位置坐标可能相同)。

因为众所周知的原因,某些妹纸之间互相喜欢,他们希望互相之间的距离至多为一个定值。但某些妹纸之间互相厌恶,他们希望互相之间的距离至少为一个定值。现在给定ML个互相喜爱的妹纸对以及他们之间距离的最大值,MD个互相厌恶的妹纸对以及他们之间距离的最小值。

你的任务是计算在满足以上条件的前提下,帮助Czy计算出编号为1和编号为N的妹纸之间距离的最大可能值。

【输入】

输入文件为 layout.in。

第一行有 3 个整数,每两个整数之间用一个空格隔开,依次表示 n,ML和DL ;

此后ML行,每行包含三个用空格分开的整数A,B和D,其中A,B满足1<=A<=B<=N。表示编号为A和B的妹纸之间的距离至多为D。

此后MD行,每行包含三个用空格分开的整数A,B和D,其中A,B满足1<=A<=B<=N。表示编号为A和B的妹纸之间的距离至少为D。

【输出】

输出文件名为 layout.out

输出文件仅包含一个整数。如果不存在任何合法的排队方式,就输出-1。如果编号1和编号N的妹纸间距离可以任意,就输出-2 。否则输出他们之间的最大可能距离。

【输入输出样例】

layout.in

layout.out

4 2 1

1 3 10

2 4 20

2 3 3

27

【数据范围】

对于40%的数据,N<=100;

对于100%的数据,N<=1000;ML,MN<=10000;D<=1000000。

题解

很明显可以看出是差分约束系统的题目,如果A和B距离至多为D则建边A->B权值为D,距离至少为D则建边B->A权值为-D。然后最短路。若有负权环则输出-1,若无法到达点N则输出-2,否则直接输出1~N的距离即可。