SRM 461 Div2 Hard NameInput

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10747&rd=14181

一列に文字が並んでおり、カーソルを左右に動かしてエンターを押すことで文字が入力できる。カーソルは文字列の右端から左端、左端から右端へ一回の移動で遷移する。入力したい文字列が与えられる。必要なカーソルの最小移動回数を求めよ。入力できないようなら-1を返すこと。

ゲーセンなんかでランキングに名前を入力するやつを思い浮かべてもらえるとわかりやすいかも。

やりかた

practice roomの回答を参考にしました。
dp[i][j]:=(i番目の文字まで入力し、カーソルが左端からj番目にあるときのカーソルの最小移動回数)とする。すると一連の移動というのは、文字列[i]と今カーソルがおいてあるj番目の文字が一緒なら頂点i+1, jにコスト0（エンターキーは移動に数えない）のエッジを張り、一緒でないなら頂点i, j+1と頂点i, j-1にコスト1のエッジを張ることであるので、グラフの問題になる。あとはiが入力したい文字列の長さと同じになるまで、幅優先探索で最短距離を求めていけばいい。

以下ソース。

int dp[2501][2501];

class NameInput {
public:
  string pred, name;

  int countUpDownKeyPresses(vector <string> predictionSequence, vector <string> nam) {
    pred="";
    name="";
    for(int i = 0; i < (int)predictionSequence.size(); i++) pred += predictionSequence[i];
    for(int i = 0; i < (int)nam.size(); i++) name += nam[i];
    memset(dp, -1, sizeof(dp));
    
    int N = pred.size(), M = name.size();
    queue<int> Q;
    Q.push(0);
    dp[0][0] = 0;
    int ans = INF;
    while(!Q.empty()){
      int u = Q.front(); Q.pop();
      int i = u / 2600; 
      int j = u % 2600;
      int d = dp[i][j];

      if(i == M){
	ans = min(d, ans);
	continue;
      }
      //next character of name
      if(name[i] == pred[j]){
	if(dp[i + 1][j] < 0){
	  dp[i + 1][j] = d;
	  Q.push((i + 1) * 2600 + j);
	}
      }

      //left-next char of pred
      int t = (j - 1 + N) % N;
      if(dp[i][t] < 0){
	dp[i][t] = d + 1;
	Q.push(i * 2600 + t);
      }
     
      //right-next char of pred
      t = (j + 1) % N;
      if(dp[i][t] < 0){
	dp[i][t] = d + 1;
	Q.push(i * 2600 + t);
      }
    }
    return ans == INF ? -1 : ans;
  }
}

なんとなくまだわかりきっていない。最短距離なのだからdpの更新のところはminを取らなくていいの？とか。また、if(i ==M)のところは

if(i == M) return d;

としても通る。うーむどういうことなのか。
多分真っ先にキューから出てくるゴールが最短なのだからminしなくてもいいってことなのだと思う。dpでminしてないのも、まっさきにその状態に遷移するときがその状態に遷移するまでの最短移動回数になるから、ということなのだろうか。。

ちなみに自分はUFOキャッチャーが好きです(´・ω・｀)。