题目背景
这本是一个非常简单的问题，然而奶牛们由于下雨已经非常混乱，无法完成这一计算，于是这个任务就交给了你。(奶牛混乱的原因看题目描述)

题目描述
在一个农场里有n块田地。某天下午，有一群牛在田地里吃草，他们分散在农场的诸多田地上，农场由m条无向的路连接，每条路有不同的长度。

突然，天降大雨，奶牛们非常混乱，想要快点去躲雨。已知每个田地都建立有一个牛棚，但是每个牛棚只能容纳一定数量的牛躲雨，如果超过这个数量，那多出的牛只能去别的田地躲雨。奶牛们每移动1的距离花费1时间，奶牛们想知道它们全部都躲进牛棚，最少需要多少时间。(即最后一头奶牛最少要花多久才能躲进牛棚)。

输入格式
第一行输入两个整数N,M。N表示田地块数，M表示路径数。

接下来N行，每行两个整数S,P，分别表示该田地现在有几头牛以及该田地的牛棚最多可以容纳多少牛。

接下来M行，每行3个整数A,B,C，表示存在一条路径连接A,B，并且它的长度为C。

输出格式
一个整数表示所有奶牛全都躲进牛棚所用的最少时间。如果无法使全部奶牛都躲进牛棚，输出-1。

输入输出样例
输入 #1复制
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
输出 #1复制
110
说明/提示
【样例解释】

1号点的两只牛直接躲进1号牛棚，剩下的5只中，4只跑去2号点，还有一只从1->2->3,3号点的2只牛也直接躲进去，这样最慢的牛花费的时间是110。

数据范围 : 对于100%的数据，N<=200 M<=1500

一般这种类型的题目有两种思路的方向：

  1. 费用流
  2. 二分+最大流

这道题是不能费用流的，因为费用流只会优先选择最短的路线，所以我们取max的费用是不可行的，因为可能平均下来更优秀。

于是我们可以考虑使用二分答案，二分当前的最大路径长度，然后我们每次加入边时值加入小于mid的边，但是还有一个问题：可能边会合并，比如1->2,2->3会合并成1->3，导致我们答案错误，所以我们需要拆点，就没有这种问题了。

这道题比较坑，没说边的范围，没开long long，一直wa

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=410,M=1e6+10;
int n,m,h[N],g[N][N],s[N],p[N],st,ed,cnt;
int head[N],nex[M],to[M],w[M],tot;
inline void ade(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
void floyd(){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)	g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
inline void init(int mid){
	tot=1; memset(head,0,sizeof head);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(g[i][j]<=mid)	add(i,j+n,inf),add(j,i+n,inf);
	for(int i=1;i<=n;i++)	add(st,i,s[i]),add(i+n,ed,p[i]),add(i,i+n,inf);
}
inline int bfs(){
	memset(h,0,sizeof h); h[st]=1; queue<int> q;	q.push(st);
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[ed];
}
int dfs(int x,int f){
	if(x==ed)	return f; int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
inline int dinic(){
	int res=0; while(bfs())	res+=dfs(st,inf);	return res;
}
int bsearch(){
	int l=0,r=inf;
	while(l<r){
		int mid=l+r>>1;	init(mid);
		if(dinic()>=cnt)	r=mid;
		else	l=mid+1;
	}
	if(r==(inf))	return -1;
	else	return l;
}
signed main(){
	scanf("%lld %lld",&n,&m); ed=2*n+1;
	for(int i=1;i<=n;i++)	scanf("%lld %lld",&s[i],&p[i]),cnt+=s[i];
	memset(g,inf,sizeof g);
	for(int i=1;i<=n;i++)	g[i][i]=0;
	while(m--){
		int a,b,c;	scanf("%lld %lld %lld",&a,&b,&c);
		g[a][b]=g[b][a]=min(g[a][b],c);
	}
	floyd();
	printf("%lld\n",bsearch());
	return 0;
}