2009 Pyramid

BFSするだけ。定数が重い？(-O2を書けないとTLE(TLは5sec)する。まあ合宿はデフォで-O2がかかっているが、それでも1.5secかかる)。多分定数8をかけているところが問題。

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
pair<int,pair<int,int> > dat[10000];
int bfs[3000][3000];
int dx[]={1,0,0,-1,1,1,-1,-1};
int dy[]={0,1,-1,0,1,-1,1,-1};
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<a;i++)
		for(int j=0;j<b;j++)
			bfs[i][j]=-1;
	for(int i=0;i<c;i++){
		int d,e,f;
		scanf("%d%d%d",&d,&e,&f);
		dat[i]=make_pair(-f,make_pair(d,e));
	}
	std::sort(dat,dat+c);
	queue<pair<int,int> >Q;
	bfs[dat[0].second.first][dat[0].second.second]=-dat[0].first;
	Q.push(make_pair(dat[0].second.first,dat[0].second.second));
	int now=1;
	while(Q.size()){
		int row=Q.front().first;
		int col=Q.front().second;
		Q.pop();
		while(-dat[now].first==bfs[row][col]){
			if(bfs[dat[now].second.first][dat[now].second.second]==-1){
				bfs[dat[now].second.first][dat[now].second.second]=-dat[now].first;
				Q.push(make_pair(dat[now].second.first,dat[now].second.second));
			}
			now++;
		}
		for(int i=0;i<8;i++){
			if(0<=row+dx[i]&&row+dx[i]<a&&0<=col+dy[i]&&col+dy[i]<b&&bfs[row+dx[i]][col+dy[i]]==-1){
				bfs[row+dx[i]][col+dy[i]]=bfs[row][col]-1;
				Q.push(make_pair(row+dx[i],col+dy[i]));
			}
		}
	}
	long long ret=0;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			ret+=bfs[i][j]==-1?0:bfs[i][j];
		//	printf("%d ",bfs[i][j]);
		}
		//printf("\n");
	}
	printf("%lld\n",ret);
}