Educational Codeforces Round 96 G問題 - Yet Another DAG Problem

Source

Educational Codeforces Round 96 G問題
Problem description

問題概要

省略

解法

省略

cLay（version 20201102-1）のコード

C++に変換後のコードはこちら

//no-unlocked
int N, w[20][20];
int mn[20], arr[20], cur[20];
ll calc(void){
  ll res = 0;
  rep(i,N) rep(j,N) if(w[i][j]) res += w[i][j] * (cur[i] - cur[j]);
  return res;
}
{
  int i, j, k, x, kk;
  ll res = ll_inf, tmp, g;
  rd(N);
  REP(rd_int()){
    rd(i--, j--, k);
    w[i][j] = k;
  }

  rep(N) rep(i,N) rep(j,N) if(w[i][j]) mn[i] >?= mn[j] + 1;
  rep(i,N) cur[i] = mn[i];
  tmp = calc();
  if(res > tmp){
    res = tmp;
    rep(i,N) arr[i] = cur[i];
  }
  for(;;){
    g = ll_inf;
    rep(k,N){
      rep(i,N) cur[i] = arr[i];
      cur[k]++;
      rep(N) rep(i,N) rep(j,N) if(w[i][j]) cur[i] >?= cur[j] + 1;
      tmp = calc();
      if(g > tmp) g = tmp, kk = k;
    }
    if(g >= res) break;
    k = kk;
    rep(i,N) cur[i] = arr[i];
    cur[k]++;
    rep(N) rep(i,N) rep(j,N) if(w[i][j]) cur[i] >?= cur[j] + 1;
    res = calc();
    rep(i,N) arr[i] = cur[i];
  }
  wt(arr(N));
}

Current time: 2024年04月26日16時38分00秒
Last modified: 2020年11月03日23時03分04秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る

Logged in as: unknown user (not login)

ログイン：