题意：一个农夫有n头牛，他希望将这些牛按照编号 1～n排成一条直线，允许有几头牛站在同一点，但是必须按照顺序，有一些牛关系比较好，希望站的距离不超过某个值，而有一些牛关系不太好，所以希望站的距离大于等于某个值，问1号牛和n号牛之间的最远距离是多少。

差分约束的裸题，对于 d[v] - d[u] ≤ w 建立权值为 w 的单向边 e(u,v)，对于 d[v] - d[u]  ≥ w 建立权值为 -w 的单向边 e(v,u)，然后再根据牛必须按顺序排列建立权值为 0 的边 e(i+1,i)，然后最短路就行了。

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn=1005; 6 const int maxm=30005; 7 const int INF=0x3f3f3f3f; 8  9 int head[maxn],nxt[maxm],point[maxm],val[maxm],size;10 int vis[maxn],dis[maxn],n,num[maxn];11 12 void add(int a,int b,int v){13     val[size]=v;14     point[size]=b;15     nxt[size]=head[a];16     head[a]=size++;17 }18 19 int spfa(){20     memset(vis,0,sizeof(vis));21     memset(dis,0x3f,sizeof(dis));22     memset(num,0,sizeof(num));23     queue
         
          q;24     vis[1]=1;25     dis[1]=0;26     q.push(1);27     while(!q.empty()){28         int u=q.front();29         q.pop();30         vis[u]=0;31         for(int i=head[u];~i;i=nxt[i]){32             int j=point[i];33             if(dis[j]>dis[u]+val[i]){34                 dis[j]=dis[u]+val[i];35                 if(!vis[j]){36                     q.push(j);37                     vis[j]=1;38                     if(++num[j]>n)return 1;39                 }40             }41         }42     }43     return 0;44 }45 46 int main(){47     int ml,md;48     scanf("%d%d%d",&n,&ml,&md);49     size=0;50     memset(head,-1,sizeof(head));51     while(ml--){52         int a,b,v;53         scanf("%d%d%d",&a,&b,&v);54         add(a,b,v);55     }56     while(md--){57         int a,b,v;58         scanf("%d%d%d",&a,&b,&v);59         add(b,a,-v);60     }61     for(int i=1;i