PKU 2227 The Wedding Juicer

http://poj.org/problem?id=2227
h*wのマスにそれぞれの高さが書かれているので、こぼれないように水を注げる最大の体積を求めろというような問題。

辺から高さを更新していくダイクストラ。
TLEもらったので入力をscanfにしてACしました。

ll in[300][300];
ll up[300][300];

main(){
  int w,h;
  scanf("%d%d",&w,&h);

  priority_queue<pair<int,PI> > q;
  rep(i,h)rep(j,w){
    scanf("%d",in[i]+j);
    if((i==0 || i==h-1) || (j==0 || j==w-1))
      q.push(mp(-in[i][j],mp(i,j)));
  }

  while(!q.empty()){
    int cc=-q.top().F;
    int cx=q.top().S.F;
    int cy=q.top().S.S;
    q.pop();
    if(up[cx][cy]) continue;
    up[cx][cy] = cc;
    rep(i,4){
      int nx=cx+dx[i],ny=cy+dy[i];
      if(min(nx,ny)<0 || nx>=h || ny>=w || up[nx][ny]) continue;
      q.push(mp(-max<ll>(cc,in[nx][ny]),mp(nx,ny)));
    }
  }
  ll ans=0;
  rep(i,h)rep(j,w)
    ans += up[i][j]-in[i][j];

  cout<<ans<<endl;
}