Codeforces Round #636 (Div. 3) E. Weights Distributing

問題概要

• 問題へのリンク

ある人が -> -> と移動する。あなたは辺の重みの候補を持っているので、ある人が旅を移動距離を最小化するように移動したときに、その移動コストを最小化するように重みを配置してください。

解説

ある地点を経由して、 -> -> -> -> へと移動すると考える。 -> が二回現れるので、そこに小さい重みを配置し、その他にさらに小さい重みを配置すればよい。

実装

提出へのリンク

int N, M, a, b, c;
vector<ll> p;
vvec<int> G;

vector<ll> dist(int s){
    queue<int> q;
    vec<bool> vis(N, false);
    vec<ll> d(N, INFLL);
    q.push(s);
    d[s] = 0;
    vis[s] = true;
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto& nv: G[v]){
            if(vis[nv])continue;
            d[nv] = d[v] + 1;
            q.push(nv);
            vis[nv] = true;
        }
    }
    return d;
}

void solve(){

    cin >> N >> M >> a >> b >> c;
    a--, b--, c--;

    p.resize(M);
    rep(i,M)cin >> p[i];
    sort(all(p));

    G.resize(N);

    rep(i,M){
        int x, y;
        cin >> x >> y;
        x--, y--;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    auto da = dist(a);
    auto db = dist(b);
    auto dc = dist(c);
    // xを中継地点として、a -> x -> b -> x -> c
    vector<ll> cum(M+1, 0);
    rep(i,M)cum[i+1] = cum[i] + p[i];
    ll ans = INFLL;
    rep(x, N){
        int idx = da[x] + db[x] + dc[x];
        if(idx > M)continue;
        ll tmp = cum[db[x]] + cum[idx];
        chmin(ans, tmp);
    }
    cout << ans << endl;
    G.clear();
    p.clear();
}

類題

atcoder.jp