SRM 353 Div1 Medium PlatformJumper

問題

足場をジャンプして渡り、コインを集めるゲームがある。足場の位置とそこにおいてあるコインの枚数が与えられる。
ゲームでは今いる足場からy座標上で下にある足場にしか移動はできない。足場は点として考えて良い。ジャンプには物理法則があり、ジャンプすると鉛直方向に初速度0、重力加速度gで移動する。水平方向にはv以下の速度でしかジャンプできない。
どの足場からゲームをスタートしてもよいとしたとき、最大で何枚のコインを集めることができるか。

やりかた

足場をノード、コイン数を辺のコストとする最小（最大）経路問題。
各足場間で移動が可能かどうか調べて、移動できるようなら、移動先の足場のコイン数をその移動のコストとする。
あとはどの足場にも移動できるスタート点と、どの足場からも移動できるゴール点を仮想的に設け、スタートからゴールに至る最大経路を求めればいい。

以下ソース。
実際には足場で得られるコイン数にマイナスをかけた最小経路問題で解いた。

class PlatformJumper {  
public:
  //足場iから足場jに移動できるなら-コイン数、できないならINFを返す
  int coin(int fx, int fy, int tx, int ty, int c, int v, int g){
    if(fy <= ty) return INF;
    ll dy = fy - ty, dx = abs(fx - tx);
    if(v * v * 2LL * dy < g * dx * dx) return INF;//整数でやらないと落ちた
    return -c;
  }
  int maxCoins(vector <string> platforms, int v, int g) {
    int x[51], y[51], c[51];
    int N = platforms.size();
    for(int i = 0; i < N; i++){
      stringstream ss(platforms[i]);
      ss >> x[i] >> y[i] >> c[i];
    }
    
    int start = N; 
    int goal = N + 1;
    int reach[55][55]; 
    for(int i = 0; i < 55; i++) fill(reach[i], reach[i] + 55, INF);
    for(int i = 0; i < N; i++){
      for(int j = 0; j < N; j++){
	if(i == j) reach[i][j] = 0;
	else reach[i][j] = coin(x[i], y[i], x[j], y[j], c[j], v, g);
      }
      reach[start][i] = -c[i];//スタート点からは各点へ移動できる
      reach[i][goal] = 0;//ゴール点へは各点から移動できる
    }
    //ワーシャルフロイド
    for(int i = 0; i <= goal; i++)
      for(int j = 0; j <= goal; j++)
	for(int k = 0; k <= goal; k++)
	  reach[i][j] = min(reach[i][j], reach[i][k] + reach[k][j]);

    return -reach[start][goal];
  }
};