题目大意
给出一个图,一些边带权,另一些边等待你赋权(最小赋为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[10010],vis[10010]; priority_queue<pair<int,int> >q; struct node { int x,y,z; }; node a[10010]; int head[20020],w[20020],to[20020],nxt[20020],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]=0; q.push(make_pair(0,s)); while(!q.empty()){ int x=q.top().second; q.pop(); if(vis[x])continue; vis[x]=1; 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=0;i<wh.size();i++){ a[wh[i]].z=1+min(mid,inf); mid-=a[wh[i]].z-1; } memset(head,0,sizeof(head)); memset(w,0,sizeof(w)); memset(to,0,sizeof(to)); memset(nxt,0,sizeof(nxt)); cnt=0; for(i=1;i<=m;i++)add(i); memset(d,0x3f,sizeof(d)); memset(vis,0,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=1;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=0,ri=inf*wh.size(); if(ck(le)>L||ck(ri)<L){ puts("NO"); return 0; } puts("YES"); while(ri-le>1){ int mid=(le+ri)>>1; if(ck(mid)<=L)le=mid; else ri=mid; } ck(le); for(i=1;i<=m;i++)printf("%lld %lld %lld\n",a[i].x-1,a[i].y-1,a[i].z); return 0; }