CF715B Complete The Graph题解

· · 题解

因为数据范围很小，一开始的思路是对每一个经过的无权边数量的方案都求一个最短路，如经过1条无权边的最短路，两条的最短路。。。

这里并不需要使经过的无权边不重复，因为我只关心这里面经过最短路小于等于L同时无权边最少的方案。容易发现这个方案一定不会有无权边被重复经过。

复杂度是 \mathrm{O(n^2\log m)} ，如果每一条边都是无权边的话可能会过不去，但没有这样的数据。结果跑过了，，

然而题解区有一个更好的 \mathrm{O(n\log m\log(mL))} 的方法。

发现同时给所有无权边加1，若存在答案且当前最短路小于 L ，则最短路长度一定至少增加1。

然后只给其中一条边加1，最短路长度最多增加1。

直接给每一个无权边定一个序号，然后二分即可。需要判一下没有无权边和达不到L的情况。

code

struct edge{
    int v,w,nxt;
}e[M<<1];
int head[N],tott;
void add(int u,int v,int w){e[++tott]={v,w,head[u]},head[u]=tott;}

struct Edge{
    int u,v,w;
}E[M];

vector<int>eg;

int st,ed;

struct hhh{
    int u,w;
    bool operator<(hhh ano)const{
        return w>ano.w;
    }
};
priority_queue<hhh>q;

int dis[N];
bool vis[N];

int dij(){
    q.push({st,0});
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[st]=0;
    while(!q.empty()){
        int u=q.top().u;
        q.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(dis[u]+w<dis[v])
                dis[v]=dis[u]+w,q.push({v,dis[v]});
        }
    }
    return dis[ed];
}

int check(int x){
    int tmp=x%eg.size();
    for(int i:eg){
        if(tmp==0)
            e[2*i-1].w=e[2*i].w=x/eg.size();
        else
            e[2*i-1].w=e[2*i].w=x/eg.size()+1,tmp--;
    }
    return dij();
}

signed main(){
    int n=read(),m=read(),L=read();st=read(),ed=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        if(w==0)
            eg.pb(i);
        add(u,v,w);add(v,u,w);
        E[i]={u,v,w};
    }
    if(eg.size()==0){
        if(dij()==L){
            printf("YES\n");
            for(int i=1;i<=m;i++)
                print(E[i].u),pc(' '),print(E[i].v),pc(' '),print(E[i].w),pc('\n');
        }else
            printf("NO\n");
        return 0;
    }
    int l=eg.size(),r=(__int128)(eg.size())*1e9,ans=-1;
    while(l<=r){
        int tmp=check(mid);
        if(tmp<=L){
            if(tmp==L)
                ans=mid;
            l=mid+1;
        }else
            r=mid-1;
    }
    if(ans==-1)
        printf("NO\n");
    else{
        int tmp=ans%eg.size();
        for(int i:eg){
            if(tmp==0)
                E[i].w=ans/eg.size();
            else
                E[i].w=ans/eg.size()+1,tmp--;
        }
        printf("YES\n");
        for(int i=1;i<=m;i++)
            print(E[i].u),pc(' '),print(E[i].v),pc(' '),print(E[i].w),pc('\n');
    }
    return 0;
}