0530 Pyon-Pyon River Crossing (ぴょんぴょん川渡り)

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0530
足場の位置とすべりやすさが与えられ，向こう岸に辿りつくルートのうち危険度の合計が最小になるときの値を求める問題．

最初はグラフとみて Dijkstra 法で解いて 00:19 sec，2988 KB で AC した．

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
using namespace std;

struct state {
  int sum_danger;
  int danger;
  int row, col;
  int jump;
  state(int s, int d, int r, int c, int j) : sum_danger(s), danger(d), row(r), col(c), jump(j) {}
  bool operator<(const state& rhs) const
  {
    return sum_danger > rhs.sum_danger;
  }
};

int main()
{
  int N, M;
  while (cin >> N >> M && N != 0) {
    vector<vector<pair<int,int> > > g(N);
    for (int i = 0; i < N; i++) {
      int k;
      cin >> k;
      for (int j = 0; j < k; j++) {
        int c, d;
        cin >> c >> d;
        g[i].push_back(make_pair(c, d));
      }
    }

    vector<vector<vector<int> > > tbl(N);
    for (int i = 0; i < N; i++) {
      tbl[i] = vector<vector<int> >(g[i].size(), vector<int>(M+1, numeric_limits<int>::max()));
    }
    priority_queue<state> q;
    for (int i = 0; i < g[0].size(); i++) {
      q.push(state(0, g[0][i].second, 0, g[0][i].first, 0));
      tbl[0][i][0] = 0;
    }
    for (int i = 0; i < g[1].size(); i++) {
      q.push(state(0, g[1][i].second, 1, g[1][i].first, 1));
      tbl[1][i][1] = 0;
    }

    int ans = numeric_limits<int>::max();
    while (!q.empty()) {
      const state s = q.top();
      q.pop();

      if (s.row+1 == N) {
        ans = min(ans, s.sum_danger);
        continue;
      }
      for (int i = 0; i < g[s.row+1].size(); i++) {
        const int next_col = g[s.row+1][i].first;
        const int next_danger = g[s.row+1][i].second;
        const int d = s.sum_danger + (s.danger + next_danger) * abs(next_col - s.col);
        if (d < tbl[s.row+1][i][s.jump]) {
          tbl[s.row+1][i][s.jump] = d;
          q.push(state(d, next_danger, s.row+1, next_col, s.jump));
        }
      }
      if (s.jump < M && s.row+2 <= N) {
        if (s.row+2 == N) {
          ans = min(ans, s.sum_danger);
        } else {
          for (int i = 0; i < g[s.row+2].size(); i++) {
            const int next_col = g[s.row+2][i].first;
            const int next_danger = g[s.row+2][i].second;
            const int d = s.sum_danger + (s.danger + next_danger) * abs(next_col - s.col);
            if (d < tbl[s.row+2][i][s.jump+1]) {
              tbl[s.row+2][i][s.jump+1] = d;
              q.push(state(d, next_danger, s.row+2, next_col, s.jump+1));
            }
          }
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}

しかし問題の制約上戻ることは無いので DP で解ける．
それでもう一度 submit して 00:07 sec，1404 KB に改善した．

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

int main()
{
  int N, M;
  while (cin >> N >> M && N != 0) {
    vector<vector<pair<int,int> > > g(N);
    for (int i = 0; i < N; i++) {
      int k;
      cin >> k;
      for (int j = 0; j < k; j++) {
        int c, d;
        cin >> c >> d;
        g[i].push_back(make_pair(c, d));
      }
    }

    vector<vector<vector<int> > > dp(N);
    for (int i = 0; i < N; i++) {
      dp[i].resize(g[i].size(), vector<int>(M+1, numeric_limits<int>::max()/2));
    }
    for (int i = 0; i < g[0].size(); i++) {
      dp[0][i][0] = 0;
    }
    for (int i = 0; i < g[1].size(); i++) {
      dp[1][i][1] = 0;
    }

    int ans = numeric_limits<int>::max();
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < g[i].size(); j++) {
        for (int m = 0; m <= M; m++) {
          if (i+1 == N) {
            ans = min(ans, dp[i][j][m]);
          } else {
            for (int k = 0; k < g[i+1].size(); k++) {
              dp[i+1][k][m] = min(dp[i+1][k][m], dp[i][j][m] + (g[i][j].second + g[i+1][k].second)*abs(g[i][j].first - g[i+1][k].first));
            }

            if (i < N-1 && m < M) {
              if (i+2 == N) {
                ans = min(ans, dp[i][j][m]);
              } else {
                for (int k = 0; k < g[i+2].size(); k++) {
                  dp[i+2][k][m+1] = min(dp[i+2][k][m+1], dp[i][j][m] + (g[i][j].second + g[i+2][k].second)*abs(g[i][j].first - g[i+2][k].first));
                }
              }
            }
          }
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}