Description
约翰的牛们非常害怕淋雨，那会使他们瑟瑟发抖．他们打算安装一个下雨报警器，并且安排了一个撤退计划．他们需要计算最少的让所有牛进入雨棚的时间． 牛们在农场的F(1≤F≤200)个田地上吃草．有P(1≤P≤1500)条双向路连接着这些田地．路很宽，无限量的牛可以通过．田地上有雨棚，雨棚有一定的容量，牛们可以瞬间从这块田地进入这块田地上的雨棚 请计算最少的时间，让每只牛都进入雨棚．
Input
第1行：两个整数F和P;
第2到F+1行：第i+l行有两个整数描述第i个田地，第一个表示田地上的牛数，第二个表示田地上的雨棚容量．两个整数都在0和1000之间．
第F+2到F+P+I行：每行三个整数描述一条路，分别是起点终点，及通过这条路所需的时间（在1和10^9之间）．
Output
一个整数，表示最少的时间．如果无法使牛们全部进入雨棚，输出-1.
题解：
首先floyd处理出点到点之间的最短时间，然后二分一个时间，网络流判断是否全部进入雨棚。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<queue>
// by zrt
// problem:
// 无论你在什么时候开始，重要的是开始以后就不要停止。
using namespace std ;
typedef long long LL ;
const double eps(1e-10) ;
const int inf(0x3f3f3f3f) ;
int f,p;
LL INF=0x3f3f3f3f3f3f3f3f;
int ni[205],fi[205];
LL map[205][205];
int S,T;
int H[404],X[340000],P[340000],tot;
int flow[340000];
int d[406];
queue<int> q;
bool bfs(){
memset(d,0,sizeof d);
d[S]=1;q.push(S);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=H[x];i;i=X[i]){
if(flow[i]>0&&!d[P[i]]){
d[P[i]]=d[x]+1;
q.push(P[i]);
}
}
}
return d[T];
}
int dfs(int x,int a){
int f=a,tmp;
if(x==T||a==0) return a;
for(int i=H[x];i;i=X[i]){
if(flow[i]>0&&d[P[i]]==d[x]+1){
tmp=dfs(P[i],min(a,flow[i]));
a-=tmp;
flow[i]-=tmp;
flow[i^1]+=tmp;
if(!a) break;
}
}
if(f==a) d[x]=-1;
// printf("%d\n",f-a);
return f-a;
}
int Dinic(){
int f=0;
while(bfs()) f+=dfs(S,inf);
return f;
}
inline void add(int x,int y,int z){
P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;
}
int sum=0;
bool judge(LL lim){
tot=1;memset(H,0,sizeof H);
for(int i=1;i<=f;i++){
add(S,i<<1,ni[i]);
add(i<<1,S,0);
add(i<<1,i<<1|1,inf);
add(i<<1|1,i<<1,0);
add(i<<1|1,T,fi[i]);
add(T,i<<1|1,0);
}
for(int i=1;i<=f;i++){
for(int j=1;j<=f;j++){
if(i!=j) {
if(map[i][j]<=lim){
add(i<<1,j<<1|1,inf);
add(j<<1|1,i<<1,0);
}
}
}
}
if(Dinic()==sum) return true;
else return false;
}
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin) ;
freopen("out.txt","w",stdout) ;
#endif
scanf("%d%d",&f,&p);
S=0,T=1; for(int i=1;i<=f;i++) scanf("%d%d",&ni[i],&fi[i]),sum+=ni[i];
memset(map,0x3f,sizeof map);
for(int i=0,x,y,z;i<p;i++){
scanf("%d%d%d",&x,&y,&z);
map[x][y]=map[y][x]=min(map[x][y],(LL)z);
// map[x][y]=z;
}
for(int k=1;k<=f;k++){
for(int i=1;i<=f;i++){
if(i==k) continue;
for(int j=1;j<=f;j++){
if(i==j||k==j) continue;
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
}
}
}
if(!judge(INF-1)) {
puts("-1");
return 0;
}
LL l=-1,r=INF-1,m;
while(r-l>1){
m=(l+r)/2;
if(judge(m)){
r=m;
}else l=m;
}
printf("%lld\n",r);
return 0 ;
}