题目大意：

有$n$头奶牛及牛棚，以及$m$条边，接下来告诉你$n$行，每行表示这个牛棚奶牛实际数目，以及能容纳的数目，接下来$m$行告诉你奶牛从一个牛棚到另一个牛棚所需要的时间，问你，是否所有奶牛能够到达牛棚，如果不能，输出$-1$，如果能，输出最短时间。

解题思路：

这种最短时间，想到了二分，是否能到达，想到了最短路径，是否能全部容纳，想到了构建一张网络图来解决。 先用$floyd$求得两块区域相通最短时间。

将点$x$拆分成$x,x'$。源点$s$连接$x$，容量为$x$的奶牛数。$x'$连接汇点$t$容量为$x$的棚子容纳数。

二分一个时间$time$，表示需要的最短时间。无论奶牛在哪个地方，只要从该点出发，距离$time$以内的点都可以到达。

所以如果$x$点到$y$点的最短时间$<=time$。那么$x$连接$y'$，容量为$INF$。

对这个二分图求最大流。如果最大流=总奶牛数量。那么表示该时间内可行。

标程

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define INF 2000000000
#define N 100010
typedef long long ll;
 
const int maxn=1100;
struct edge{
    int u,v,next,cap;
}e[maxn*maxn];
int n,head[N],tol,top,st[N];
int src,des,dep[N],gap[N];
 
void adde(int u,int v,int c){
    e[tol].u=u,e[tol].v=v,e[tol].next=head[u],e[tol].cap=c,head[u]=tol++;
    e[tol].u=v,e[tol].v=u,e[tol].next=head[v],e[tol].cap=0,head[v]=tol++;
}
 
void bfs(){//对于反边计算层次
    for(int i=0;i<N;i++) dep[i]=N-1;
    memset(gap,0,sizeof gap);
    gap[0]=1,dep[des]=0;
    int q[N],l=0,r=0,u,v;
    q[r++]=des;
    while(l!=r){
        u=q[l++];
        l=l%N;
        for(int i=head[u];i!=-1;i=e[i].next){
            v=e[i].v;
            if(e[i].cap!=0||dep[v]!=N-1) continue;
            q[r++]=v;
            r=r%N;
            ++gap[dep[v]=dep[u]+1];
        }
    }
}
 
int sap(){
    bfs();
    int u=src,s[N],top=0,res=0,ii;
    int cur[N];
    memcpy(cur,head,sizeof head);
    while(dep[src]<n){
        if(u==des){//求得一条增广路
           int minf=INF,pos=n;
           for(int i=0;i<top;i++){
              if(minf>e[s[i]].cap){
                  minf=e[s[i]].cap;
                  pos=i;
              }
           }
           for(int i=0;i<top;i++){
              e[s[i]].cap-=minf;
              e[s[i]^1].cap+=minf;
           }
           top=pos;
           res+=minf;
           u=e[s[top]].u;//优化1
        }
        if(dep[u]!=0&&gap[dep[u]-1]==0) break;//出现断层
        ii=-1;
        for(int i=cur[u];i!=-1;i=e[i].next){
             if(dep[e[i].v]==N-1) continue;
             if(e[i].cap!=0&&dep[u]==dep[e[i].v]+1){ii=i;break;}
        }
        if(ii!=-1){//有允许弧
            cur[u]=ii;
            s[top++]=ii;
            u=e[ii].v;
        }else{//不断回退找增光路
            int mind=n;
            for(int i=head[u];i!=-1;i=e[i].next){
                if(e[i].cap==0) continue;
                if(dep[e[i].v]<mind) mind=dep[e[i].v],cur[u]=i;
            }
            --gap[dep[u]];
            ++gap[dep[u]=mind+1];//优化2
            if(u!=src) u=e[s[--top]].u;
        }
    }
    return res;
}
 
const ll inf=1e18;
int nn,m,now[maxn],need[maxn],sum;
ll dis[maxn][maxn],maxr;
 
void initial(){
    sum=0;
    for(int i=0;i<=nn;i++){
        for(int j=0;j<=nn;j++){
            dis[i][j]=inf;
        }
        dis[i][i]=0;
    }
}
 
void input(){
    for(int i=1;i<=nn;i++){
        scanf("%d%d",&now[i],&need[i]);
        sum+=now[i];
    }
    for(int i=0;i<m;i++){
        int u,v,x;
        scanf("%d%d%d",&u,&v,&x);
        maxr+=x;
        if(x<dis[u][v]){
            dis[u][v]=dis[v][u]=x;
        }
    }
    for(int k=1;k<=nn;k++){
        for(int i=1;i<=nn;i++){
            for(int j=1;j<=nn;j++){
                if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    maxr=0;
    for(int i=1;i<=nn;i++){
        for(int j=1;j<=nn;j++){
            if(dis[i][j]!=inf && dis[i][j]>maxr) maxr=dis[i][j];
        }
    }
}
 
void build(ll c){
	tol=0;
    memset(head,-1,sizeof head);
	src=1,des=2*nn+2,n=2*nn+2;
	for(int i=1;i<=nn;i++){
        adde(src,i+1,now[i]);
        adde(i+nn+1,des,need[i]);
	}
	for(int i=1;i<=nn;i++){
        for(int j=1;j<=nn;j++){
            if(dis[i][j]<=c) adde(i+1,j+nn+1,INF);
        }
	}
}
 
void solve(){
    ll l=0,r=maxr;
    build(r);
    if(sap()<sum){
        printf("-1\n");
        return;
    }
    while(l<r){
        ll mid=(l+r)/2;
        build(mid);
        if(sap()>=sum) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
}
 
int main(){
    scanf("%d%d",&nn,&m);
    initial();
    input();
    solve();
    return 0;
}