PKU 2110 Mountain Walking
http://poj.org/problem?id=2110
n*nの格子上の点があり、それぞれの点は高さを持っている。
最初(1,1)にいて、上下左右に移動して(n,n)の点にたどり着きたい。
ここで移動途中の点の高さの最大値と最小値の差の最小値を求めろというような問題。
最初あるノードにたどり着いたときのそれまでの高さと低さの差を保持してダイクストラしたらWA。
それまでに訪れた高さの最高値と最小値を保持するとMLEやTLE。
仕方ないので、ある高さまでしか下がれないとしたときに、どの程度の高さまで登らなければならないかを高さごとに計算することでなんとかACしました。
int in[100][100]; bool vis[10000]; int n; int dj(int l){ priority_queue<pair<int,int> >q; q.push(mp(-in[0][0],0)); memset(vis,0,sizeof(vis)); while(!q.empty()){ int hh=-q.top().F,v=q.top().S; q.pop(); if(vis[v])continue; vis[v]=true; int x=v/n,y=v%n; if(v==n*n-1){ return hh; } rep(i,4){ int nx=x+dx[i],ny=y+dy[i]; int nv=nx*n+ny; int nh=max(hh,in[nx][ny]); if(in[nx][ny]<l)continue; if(nx<0 || n<=nx || ny<0 || n<=ny || vis[nv])continue; q.push(mp(-nh,nv)); } } return 1000; } main(){ cin>>n; rep(i,n)rep(j,n)cin>>in[i][j]; int ans=1000; for(int i=in[0][0];i>=0;i--){ ans=min(ans,dj(i)-i); } cout<<ans<<endl; }