715B Complete The Graph

传送门

题目大意

给出一个图,一些边带权,另一些边等待你赋权(最小赋为1).请你找到一种赋权方式,使得 s 到 t 的最短路为 L
n ≤ 1e3 ,m ≤ 1e4 ,L ≤ 1e9

分析

二分所有边的边权和

使得二分后第p条边权值为k,1~p-1条边权值为inf,剩余边权值为1

对于每种情况跑一次最短路

如果结果小于L则增大点权和否则减少

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

#define int long long

const int inf = 0x3f3f3f3f;

int n,m,s,t,L,d[],vis[];

priority_queue<pair<int,int> >q;

struct node {

    int x,y,z;

};

node a[];

int head[],w[],to[],nxt[],cnt;

vector<int>wh;

inline void add(int i){

    int x=a[i].x,y=a[i].y,z=a[i].z;

    nxt[++cnt]=head[x];

    head[x]=cnt;

    to[cnt]=y;

    w[cnt]=z;

    nxt[++cnt]=head[y];

    head[y]=cnt;

    to[cnt]=x;

    w[cnt]=z;

}

inline void dij(){

    d[s]=;

    q.push(make_pair(,s));

    while(!q.empty()){

      int x=q.top().second;

      q.pop();

      if(vis[x])continue;

      vis[x]=;

      for(int i=head[x];i;i=nxt[i]){

          int y=to[i],z=w[i];

          if(d[y]>d[x]+z){

            d[y]=d[x]+z;

            q.push(make_pair(-d[y],y));

          }

      }

    }

}

inline int ck(int mid){

    int i,j,k;

    for(i=;i<wh.size();i++){

      a[wh[i]].z=+min(mid,inf);

      mid-=a[wh[i]].z-;

    }

    memset(head,,sizeof(head));

    memset(w,,sizeof(w));

    memset(to,,sizeof(to));

    memset(nxt,,sizeof(nxt));

    cnt=;

    for(i=;i<=m;i++)add(i);

    memset(d,0x3f,sizeof(d));

    memset(vis,,sizeof(vis));

    dij();

    return d[t];

}

signed main(){

    int i,j,k;

    scanf("%lld%lld%lld%lld%lld",&n,&m,&L,&s,&t);

    s++,t++;

    for(i=;i<=m;i++){

      scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].z);

      a[i].x++,a[i].y++;

      if(!a[i].z)wh.push_back(i);

    }

    int le=,ri=inf*wh.size();

    if(ck(le)>L||ck(ri)<L){

      puts("NO");

      return ;

    }

    puts("YES");

    while(ri-le>){

      int mid=(le+ri)>>;

      if(ck(mid)<=L)le=mid;

        else ri=mid;

    }

    ck(le);

    for(i=;i<=m;i++)printf("%lld %lld %lld\n",a[i].x-,a[i].y-,a[i].z);

    return ;

}