問題 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; }