传送门

题目大意

给出一个图,一些边带权,另一些边等待你赋权(最小赋为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 ;
}

最新文章

  1. ROS 使用自带和usb摄像头获取图像
  2. [CareerCup] 1.7 Set Matrix Zeroes 矩阵赋零
  3. pch找不到pod里头文件
  4. vb.net 动态调用api
  5. ovs router
  6. 一个小玩具:Python调用Mysql
  7. ThinkPhp调用webservice
  8. AngularJS_百度百科
  9. crontab的定时任务不能自动执行,但是手动执行脚本一直能成功
  10. OpenGL教程(0)——介绍
  11. Linux查看内存占用情况
  12. mybatis 在xml文件中获取当前时间的sql
  13. 20175305张天钰 《java程序设计》第四周课下测试总结
  14. Spring boot整合Mybatis
  15. tp3.2 上传文件及下载文件
  16. Nodejs脚手架搭建基于express的应用
  17. 用eclipse导入打war包的maven项目
  18. Python开发【笔记】:从海量文件的目录中获取文件名--方法性能对比
  19. Spring 注解 hibernate 实体方法 &lt;property name=&quot;packagesToScan&quot; value=&quot;com.sise.domain&quot;/&gt;
  20. Jersey 2.x 服务器端应用支持的容器

热门文章

  1. python_编码集的介绍
  2. 1.Linux下Git入门学习
  3. 第二篇 Mysql常用操作记录(转载)
  4. CentOS7安装wget 及配置
  5. hihoCoder#1181(欧拉路径)
  6. JQ选择器大全
  7. __cdecl &amp; __stdcall calling conventions
  8. [置顶] 制作开机LOGO就是这么简单!
  9. CKEditor 自定义按钮插入服务端图片
  10. Visual Studio 小工具