読者です 読者をやめる 読者になる 読者になる

UVa12295 Optimal Symmetric Paths

解説
解法が右往左往した問題。
左上半分と右下半分のコストの和を1つのコストとみなして、ダイクストラする。ある状態における最小のコストが更新できなくても等しいのであれば場合の数をカウントする必要がある。その場合にダイクストラの処理を打ち切らずに回してしまうと TLE を起こすので、ある位置におけるコストと既知の最小コストとが等しいときは、場合の数のみをカウントをしてダイクストラの処理は打ち切らないといけない。

#include <iostream>
#include <queue>

using namespace std;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int N;
int F[110][110];

struct State
{
  int cost, x, y;
  bool operator < (const State& rhs) const {
    return cost > rhs.cost;
  }
};

int const MOD = (int)1e9+9;
int const INF = 1<<29;

#define SYM(y, x) F[N-x-1][N-y-1]
#define COST(y, x) ( (x+y == N-1) ? F[y][x] : F[y][x]+SYM(y,x) )

int const dx[] = {-1,0,1,0};
int const dy[] = {0,-1,0,1};

inline bool valid_range(int x, int y) {
  return 0<=x&&x<N && 0<=y&&y<N;
}

int solve() {
  
  int dist[110][110];
  rep(i, 110) rep(j, 110) dist[i][j] = INF;
  dist[0][0] = COST(0,0);
  priority_queue<State> pq;
  pq.push((State){dist[0][0],0,0});
  
  int ways[110][110] = {};
  ways[0][0] = 1;
  
  while(!pq.empty()) {
    State st = pq.top(); pq.pop();
    
    if(st.x+st.y == N-1) continue;
    
    rep(k, 4) {
      int ny = st.y+dy[k], nx = st.x+dx[k];
      if(!valid_range(nx, ny)) continue;
      int ncost = st.cost+COST(ny,nx);
      if(dist[ny][nx] == ncost) {
        ( ways[ny][nx] += ways[st.y][st.x] ) %= MOD;
      }
      if(dist[ny][nx] <= ncost) continue;
      ways[ny][nx] = ways[st.y][st.x];
      dist[ny][nx] = ncost;
      pq.push((State){ncost,nx,ny});
    }
  }
  
  int mindist = INF;
  rep(i, N) mindist = min(mindist, dist[i][N-i-1]);
  
  int ret = 0;
  rep(i, N) if(dist[i][N-i-1] == mindist) {
    ( ret += ways[i][N-i-1] ) %= MOD;
  }
  return ret;
}

int main() {
  
  while(cin >> N && N) {
    rep(i, N) rep(j, N)
      cin >> F[i][j];
    cout << solve() << endl;
  }

  return 0;
}