AtCoder Regular Contest 035 C問題 - アットコーダー王国の交通事情

Source

AtCoder Regular Contest 035
問題文

問題概要

省略

解法

省略

cLay（version 20191123-1）のコード

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

int N, A, B, C;
int dp[400][400];
{
  int d;
  ll res = 0;

  rd(N);
  rep(i,N) rep(j,N) dp[i][j] = int_inf;
  rep(i,N) dp[i][i] = 0;
  REP(rd_int()){
    rd(A--,B--,C);
    dp[B][A] = (dp[A][B] <?= C);
  }
  rep(k,N) rep(i,N) rep(j,i+1,N) dp[j][i] = (dp[i][j] <?= dp[i][k] + dp[k][j]);
  rep(i,N) rep(j,i+1,N) res += dp[i][j];

  REP(rd_int()){
    rd(A--,B--,C);
    rep(i,N) rep(j,i+1,N){
      d = dp[i][j] - min(dp[i][A] + C + dp[B][j], dp[i][B] + C + dp[A][j]);
      if(d > 0){
        dp[i][j] -= d;
        dp[j][i] -= d;
        res -= d;
      }
    }
    wt(res);
  }
}

Current time: 2024年04月26日20時53分38秒
Last modified: 2019年11月23日19時13分36秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Regular_Contest ARC035 ARC_C
トップページに戻る

Logged in as: unknown user (not login)