我%……&（￥……，调了一下午，最后发现P赋值1e5能过，赋值1e6就会TLE致死。改了一下午加一晚上然而这是为什么？？？

一种常见的建图套路，首先二分答案，注意上界要取大一点，1e9是不行的。然后问题变为判定，首先弗洛伊德求出点两两之间的最短距离。每次建图时把点拆成两个，然后s向所有的i连容量为a[i]的边，所有i+n向t连容量为b[i]的边。对于原图中的一条边(u,v)，如果长度小于等于当前二分的mid的，连接u和v+n，容量为inf。（因为可以同时走）

记得来long long

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const long long P=100005,inf=1e12;long long n,m,h[P],cnt=1,a[P],b[P],s,t,sum,le[P],d[233][233];struct qwe{    long long ne,to,va;}e[P];long long read(){    long long r=0,f=1;    char p=getchar();    while(p>'9'||p<'0')    {        if(p=='-')            f=-1;        p=getchar();    }    while(p>='0'&&p<='9')    {        r=r*10+p-48;        p=getchar();    }    return r*f;}void add(long long u,long long v,long long w){    cnt++;    e[cnt].ne=h[u];    e[cnt].to=v;    e[cnt].va=w;    h[u]=cnt;}void ins(long long u,long long v,long long w){    add(u,v,w);    add(v,u,0);}bool bfs(){    queue
        
         q;    memset(le,0,sizeof(le));    le[s]=1;    q.push(s);    while(!q.empty())    {        long long u=q.front();        q.pop();        for(long long i=h[u];i;i=e[i].ne)            if(e[i].va>0&&!le[e[i].to])            {                le[e[i].to]=le[u]+1;                q.push(e[i].to);            }    }    return le[t];}long long dfs(long long u,long long f){    if(u==t||!f)        return f;    long long us=0;    for(long long i=h[u];i&&us
         
          0&&le[e[i].to]==le[u]+1) { long long t=dfs(e[i].to,min(e[i].va,f-us)); e[i].va-=t; e[i^1].va+=t; us+=t; } if(!us) le[u]=0; return us;}long long dinic(){ long long re=0; while(bfs()) re+=dfs(s,inf); return re;}bool ok(long long p){ memset(h,0,sizeof(h)); cnt=1; for(long long i=1;i<=n;i++) ins(s,i,a[i]),ins(i+n,t,b[i]); for(long long i=1;i<=n;i++) for(long long j=1;j<=n;j++) if(d[i][j]<=p) ins(i,j+n,inf); return dinic()==sum;}int main(){ scanf("%d%d",&n,&m); s=0,t=2*n+1; for(long long i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); sum+=a[i]; } for(long long i=1;i<=n;i++) for(long long j=1;j<=n;j++) d[i][j]=inf; for(long long i=1;i<=n;i++) d[i][i]=0; for(long long i=1;i<=m;i++) { long long x,y; long long z; scanf("%d%d%lld",&x,&y,&z); d[x][y]=d[y][x]=min(d[x][y],z); } for(long long k=1;k<=n;k++) for(long long i=1;i<=n;i++) for(long long j=1;j<=n;j++) if(d[i][j]>d[i][k]+d[k][j]) d[i][j]=d[i][k]+d[k][j]; long long l=-1,r=inf; while(r-l>1) { long long mid=(l+r)>>1; if(ok(mid)) r=mid; else l=mid; } printf("%lld",r==inf?-1:r); return 0;}