Bayan 2015 Contest Elimination : E - Water Barrels

こちらもなかなか面白かった。本番１発正答だったしね。
http://contest.bayan.ir/en/contest/elimination_2014/problem/E/

問題

底面積が1m^2、高さが無限のN個のタンクがある。
ここにN個のタンクを結ぶM本のパイプがある。
各パイプはX[i]番とY[i]番のタンクを高さH[i]mで接続する。

ここで、１番のタンクに毎秒1m^3の水を注ぎこむ。
各タンクに最初の１滴の水が入る時刻を答えよ。
なお、パイプは十分に細いのでパイプ自体の体積は無視でき、かつ水がパイプを移動する時間も無視できる。

解法

初期状態では１番のタンクのみ水が到達可能である。

既に水が到達可能なタンクがある場合、以下のように水が満たされていく。

• 水が最低位のタンクが同列でp個あるとすると、それらのタンクは１秒で1/p(m)ずつ水位が増す。言い換えるとp秒で1m水位が増す。
• これら最低位のタンクのいずれかがパイプの高さに到達し、かつパイプの先が水が未到達のタンクの場合、以後そこのタンクも水が到達可能となる。

上記考察をもとに、水が全タンクに到達可能となるまで、最低位のタンクにp秒で1m水を増していき、パイプに到達するたび最低位のタンクの数を再計算していけば良い。

int N,M;
int X[1001],Y[1001],H[1001],TH[1001];
priority_queue<pair<int,int> > E[1001];
ll T[1001];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,1001) while(E[i].size()) E[i].pop();
	FOR(i,1001) T[i]=1LL<<40;
	T[0]=0;
	
	ZERO(TH);
	cin>>N>>M;
	FOR(i,M) {
		cin>>X[i]>>Y[i]>>H[i];
		E[X[i]-1].push(make_pair(-H[i],Y[i]-1));
		E[Y[i]-1].push(make_pair(-H[i],X[i]-1));
	}
	
	ll tot=0;
	int np=1;
	
	while(np<N) {
		int mh=10000000;
		FOR(i,N) if(T[i]<1LL<<40) mh=min(mh,TH[i]);
		
		int num=0;
		pair<int,int> ev;
		ev.first=-9999999;
		x=-1;
		FOR(i,N) if(T[i]<1LL<<40 && TH[i]==mh) {
			num++;
			if(E[i].size() && ev.first<E[i].top().first) ev=E[i].top(), x=i;
		}
		ev.first*=-1;
		E[x].pop();
		tot+=(ev.first-mh)*(ll)num;
		FOR(i,N) if(T[i]<1LL<<40 && TH[i]==mh) TH[i]=ev.first;
		if(T[ev.second]==1LL<<40) T[ev.second]=tot;
		
		np=0;
		FOR(i,N) np+=T[i]<(1LL<<40);
	}
	FOR(i,N) _P("%lld%s", T[i],(i==(N-1))?"\n":" ");
	
}

まとめ

最終的に自力で１発正答できたこともあり楽しめた。