AtCoder Beginner Contest 144 F問題 - Fork in the Road

Source

AtCoder Beginner Contest 144
問題文

問題概要

省略

解法

省略

cLay（version 20191027-1）のコード

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

int N, M, A[18d4], B[18d4];
double dp[600], p[600];

{
  double mx = 0, s, m;
  graph g;
  rd(N,M,(A--,B--)(M));
  g.setDirectEdge(N,M,A,B);

  p[0] = 1;
  rep(i,N) rep[g.edge[i]](j,g.es[i]) p[j] += p[i] / g.es[i];
  rrep(i,N-1){
    rep[g.edge[i]](j,g.es[i]) dp[i] += dp[j];
    dp[i] = dp[i] / g.es[i] + 1;
  }

  rep(i,N) if(g.es[i] > 1){
    s = m = 0;
    rep[g.edge[i]](j,g.es[i]){
      s += dp[j];
      m >?= dp[j];
    }
    mx >?= p[i] * (s/g.es[i] - (s-m)/(g.es[i]-1));
  }

  wt(dp[0] - mx);
}

Current time: 2024年04月26日19時48分57秒
Last modified: 2019年11月01日20時24分18秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC144 ABC_F
トップページに戻る

Logged in as: unknown user (not login)