大意： n头牛编号为1到n，按照编号的顺序排成一列，每两头牛的之间的距离 >= 0。这些牛的距离存在着一些约束关系：1.有ml组（u, v, w）的约束关系，表示牛[u]和牛[v]之间的距离必须 <= w。2.有md组（u, v, w）的约束关系，表示牛[u]和牛[v]之间的距离必须 >= w。问如果这n头无法排成队伍，则输出-1，如果牛[1]和牛[n]的距离可以无限远，则输出-2，否则则输出牛[1]和牛[n]之间的最大距离。
我们假设(u)<(v)。 对u,v做ml处理时，题目有dis[v]-dis[u]<=w; 即dis[u]+w>=dis[v]，所以这里要从u到v建一条长度为w的边。
对u,v做md处理时，题目有dis[v]-dis[u]>=w; 即dis[v]+(-w)>=dis[u]，所以这里要从v到u建一条长度为-w的边。
然后求最短路即可。
特殊情况： 负环存在时取最小值会导致一个点必须要在自己前面，但那是不可能的事（输出-1）。 当dis[n]没有改变时说明1和n没有联系，即可以无穷大（输出-2）。
我的代码比较凌乱，不是很方便看懂。 （不是很理解我即便很浪费空间也不至于多花别人十几倍啊）
/* memory:4088k time:32ms */ #include<cstdio> #include<cstring> using namespace std; #define N 1010 int n,ml,md,w[N][N]; int dis[N],cnt[N],que[N]; bool in[N]; inline void uni(int x) { int a,b,dis; scanf("%d%d%d",&a,&b,&dis); if((a>b)^(x==-1)) a^=b^=a^=b; w[a][b]=dis*x; } int spfa() { int hd=1,tl=1; que[hd]=1; dis[1]=0; while(hd<=tl) { int x=que[hd++%N]; in[x]=0; for(int i=1; i<=n; i++) { int len=dis[x]+w[x][i]; if(w[x][i]&&len<dis[i]) { dis[i]=len; if(!in[i]) { in[i]=1; que[++tl%N]=i; if(++cnt[i]>=n) return -1; } } } } if(dis[n]==522133279) return -2; return dis[n]; } int main() { memset(dis,31,sizeof(dis));//522133279 scanf("%d%d%d",&n,&ml,&md); while(ml--) uni(1); while(md--) uni(-1); printf("%d",spfa()); }