UVA 929

問題 http://uva.onlinejudge.org/external/9/929.html

久しぶりに師匠と一緒に解いた問題(ICPC練習回)

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<string>
#include<queue>
#include<deque>
#include<climits>
#include<numeric>
#include<functional>
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define fi(i,j,k) fill(i[0],i[0]+j*j,k)
#define smax 1000
typedef long long ll;
using namespace std;
typedef pair<int,int> P;
#define INF 1<< 25
 
int a[smax][smax];
int table[smax][smax];
int h,w;
 
struct S{
   int x,y,c;
   bool operator<(const S &s)const{
      return c > s.c;
   }
};
 
int bfs(){
   S s;
   s.x = s.y = s.c = 0;
   int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
   priority_queue<S> que;
   fi(a,smax,INF);
   s.c = table[0][0];
   que.push(s);
   a[0][0] = table[0][0];
   while(!que.empty()){
      s = que.top();
      que.pop();
      if(s.x == w-1 && s.y == h-1) break;
      rep(i,4){
         int xx =s.x+dx[i],yy=s.y+dy[i];
         if(0 <= xx && xx < w && 0 <= yy && yy < h){
            int temp = a[s.y][s.x]+table[yy][xx];
            if(temp < a[yy][xx]){
               S ss;
               ss.x = xx;
               ss.y = yy;
               a[yy][xx] = a[s.y][s.x]+table[yy][xx];
               ss.c = a[yy][xx];
               que.push(ss);
            }
         }
      }
   }
   return a[h-1][w-1];
}
  
int main(void){
   int n;
   cin >> n;
   rep(x,n){
      fi(table,smax,0);
      fi(a,smax,0);
      cin >> h >> w;
      rep(i,h) rep(j,w) cin >> table[i][j];
      cout << bfs() << endl;
   }
   return 0;
}