裏紙

ほぼ競プロ、たまに日記

CF 716 D - Complete The Graph

問題

Problem - D - Codeforces

問題概要

n頂点m辺の無向グラフがある。辺にはそれぞれ重みがあり、その重さは正の整数である。いくつかの辺の重みがわからなくなってしまったので、その辺に重みを付け直したい。ただし、頂点sから頂点tへの最短経路はLでなければならない。

そのような方法がない場合はNOと出力し、ある場合にはYESと出力して全ての辺の重さを出力せよ。

  •  1 \le n \le 1000
  •  1 \le m \le 10000
  •  0 \le s,t \le n-1 , s \neq t
  •  1 \le L \le 10^9

イデア

この問題は不可能な状況を考えなければ単純に考えていくことが出来る。というわけでまずは解が存在する時はどのような状況なのかを考えてみる。

まず、重みがわからなくなってしまった辺を存在しないものとして考え、既にわかっている辺のみでのsからtへの最短経路を計算してみて、その距離がL未満ならばその他の辺をどのように設定しても不可能であることが明らかなので、解が存在しないということがわかる。

そして、次に重みがわからなくなってしまった辺の重さを全て1に設定して最短経路を計算してみる。すると、sからtへの最短経路としてあり得る値の中で最小値が求まることは簡単にイメージできる。つまり、この値がLよりも大きくなってしまったらこれ以上小さく出来ないのだからその時も解が存在しないということがわかる。

この2つの判定に引っかからなければ、何らかの形で解が存在するということになる。全てのsからtへのパス上に未定辺が1つあると仮定したときに、はじめは全ての未定の辺に重さ1を割り当てておいて最短経路を探す。それがLに一致すれば終了し、一致しない時は最短経路上の未定だったどれか1つの辺の重さを1増やす。すると、経路は変わるかもしれないが、最短経路は1増えることになる。これを繰り返していくことでいずれは最短経路の距離はLになっていくのが分かる。

それでは、どのようにして効率よく重みを割り当てていけばよいのかということを考えてみる。上で述べたことに似たようなことをする。まずは未定辺をはじめ全て重さ1にしておき、まずその状態でsからtへの最短経路を求める。この経路上に未定辺が無かった場合、この経路の長さがLでなければならない。もしある時には、その経路長はL未満であるはずである。

ここで、最短経路上には無い未定辺の重みをINFに再設定して再びsからtへの最短経路を求める。そして、その最短経路上の未定辺を上手く設定して最短経路長をLになるようにしていきたい。どのようにするかというと、最短経路長がL未満である限り、その経路上の1つの未定辺を適当にいじってLになるようにとりあえずしてみる。そしてまた最短経路を計算し直す。これを繰り返していくことでいずれはLへ近づいていき一致するはずである。そして、この繰り返しの回数はO(n)回に収まる。最初に発見した最短経路上の辺しかいじらないので、変更することになる辺の個数がO(n)本になる。そしてこの辺の重みの変更は各辺に対して1回ずつしか行われないからである。

ということで最短経路の計算にDijkstra法を利用することで全体の計算量はO(nmlogn)となり、間に合う。Editorialには、n,m \le 10^5でも実は解けるということについて言及されている。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;

const int N=1000, M=10000;
const ll INF=123456789012345LL;

int U[M], V[M], W[M];

struct edge{int to,cost;};
vector<edge> G1[N], G2[N];
ll d1[N], d2[N];
int par[N];

// 0:存在しない, -1:未定辺, -2:最短経路に含まれる未定辺
ll ans[N][N]={0};

int main()
{
    int n,m,L,s,t;
    scanf(" %d %d %d %d %d", &n, &m, &L, &s, &t);

    rep(i,m)
    {
        int u,v,w;
        scanf(" %d %d %d", &u, &v, &w);
        if(w==0)
        {
            G2[u].pb(edge{v,1});
            G2[v].pb(edge{u,1});
            ans[u][v]=ans[v][u]=-1;
        }
        else
        {
            G1[u].pb(edge{v,w});
            G1[v].pb(edge{u,w});
            G2[u].pb(edge{v,w});
            G2[v].pb(edge{u,w});

            ans[u][v]=ans[v][u]=w;
        }

        U[i]=u;
        V[i]=v;
        W[i]=w;
    }

    priority_queue<pi,vector<pi>,greater<pi>> que;

    // 未定辺を含まないグラフでの最短経路
    // dijkstra
    fill(d1,d1+N,INF);
    d1[s]=0;
    que.push(pi(0,s));
    while(!que.empty())
    {
        pi p=que.top();
        que.pop();
        int v=p.se;
        if(d1[v]<p.fi) continue;
        rep(i,G1[v].size())
        {
            edge e=G1[v][i];
            if(d1[e.to]>d1[v]+e.cost)
            {
                d1[e.to]=d1[v]+e.cost;
                que.push(pi(d1[e.to],e.to));
            }
        }
    }

    if(d1[t]<L)
    {
        printf("NO\n");
        return 0;
    }
    if(d1[t]==L)
    {
        printf("YES\n");
        rep(i,m)
        {
            int u=U[i], v=V[i];
            ll d=ans[u][v];
            if(d<0) d=INF;
            printf("%d %d %lld\n", u, v, d);
        }
        return 0;
    }

    // 未定辺の重みを全て1にしたグラフでの最短経路
    // dijkstra
    fill(d2,d2+N,INF);
    d2[s]=0;
    que.push(pi(0,s));
    memset(par,-1,sizeof(par));
    while(!que.empty())
    {
        pi p=que.top();
        que.pop();
        int v=p.se;
        if(d2[v]<p.fi) continue;
        rep(i,G2[v].size())
        {
            edge e=G2[v][i];
            if(d2[e.to]>d2[v]+e.cost)
            {
                d2[e.to]=d2[v]+e.cost;
                que.push(pi(d2[e.to],e.to));
                // 経路復元のために親を記録
                par[e.to]=v;
            }
        }
    }

    if(d2[t]>L)
    {
        printf("NO\n");
        return 0;
    }

    int now=t;
    while(now!=s)
    {
        int nx=par[now];
        if(ans[now][nx]==-1) ans[now][nx]=ans[nx][now]=-2;
        now=nx;
    }
    // 最短経路に関係ない未定辺を全てINFに設定
    rep(i,N)rep(j,N)
    {
        if(ans[i][j]==-1) ans[i][j]=INF;
    }
    // もどしておく
    rep(i,N)rep(j,N)
    {
        if(ans[i][j]==-2) ans[i][j]=-1;
    }

    // 最短経路がLに一致するまでやる
    while(1)
    {
        // dijkstra
        fill(d2,d2+N,INF);
        d2[s]=0;
        que.push(pi(0,s));
        memset(par,-1,sizeof(par));
        while(!que.empty())
        {
            pi p=que.top();
            que.pop();
            int v=p.se;
            if(d2[v]<p.fi) continue;
            rep(i,G2[v].size())
            {
                edge e=G2[v][i];
                int cost=ans[v][e.to];
                if(d2[e.to]>d2[v]+abs(cost))
                {
                    d2[e.to]=d2[v]+abs(cost);
                    que.push(pi(d2[e.to],e.to));
                    // 経路復元のために親を記録
                    par[e.to]=v;
                }
            }
        }

        if(d2[t]==L) break;

        now=t;
        while(now!=s)
        {
            int nx=par[now];

            // 未定辺
            if(ans[now][nx]<0)
            {
                ll dist=abs(ans[now][nx]);
                ans[now][nx]=ans[nx][now]=dist+(L-d2[t]);
                break;
            }

            now=nx;
        }
    }


    printf("YES\n");
    rep(i,m)
    {
        int u=U[i], v=V[i];
        ll d=abs(ans[u][v]);
        printf("%d %d %lld\n", u, v, d);
    }
    return 0;
}