715B Complete The Graph-白红宇

715B Complete The Graph

阅读量：6040 次

发布时间：2019-06-20

本文共 1307 字，大约阅读时间需要 4 分钟。

题目大意

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

n ≤ 1e3 ,m ≤ 1e4 ,L ≤ 1e9

分析

二分所有边的边权和

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

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

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

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define int long longconst int inf = 0x3f3f3f3f;int n,m,s,t,L,d[10010],vis[10010];priority_queue
                   
                    
                      >q;struct node { int x,y,z;};node a[10010];int head[20020],w[20020],to[20020],nxt[20020],cnt;vector
                     
                      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
                      
                       L||ck(ri)
                       
                        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;}