AtCoder ARC #025 : C - ウサギとカメ

最近C問題の難易度上がってるような。
http://arc025.contest.atcoder.jp/tasks/arc025_3

問題

N頂点の無向辺距離付の連結グラフが与えられる。
ここをウサギは速度R、カメは速度Tで移動する。
N頂点中の３要素(A,B,C)のうち、カメがC→Aに移動する時間がウサギがB→Aに移動する時間より速くなるような(A,B,C)の組み合わせ数を求めよ。

解法

ゴール地点Aに対して総当たりしていく。
Aに対し、Dijkstra法で各頂点への距離を求める。
次に、Cを総当たりしたうえでB→Aの距離がC→AのR/T倍より大きいものの個数を求める。
最後のBの数え上げは尺取法でもよいし、下記の通りupper_boundで処理しても良い。

Dijkstra１回がO((N+M)logN)、CとBの数え上げがO(NlogN)なので、全体では(N*(N+M)*logN)と少し重め。

int N,M,R,T;
ll D[4000];
vector<pair<ll,int> > E[3000];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>R>>T;
	FOR(i,M) {
		cin>>x>>y>>j;
		E[x-1].push_back(make_pair(1LL*j*R*T,y-1));
		E[y-1].push_back(make_pair(1LL*j*R*T,x-1));
	}
	
	ll ret=0;
	FOR(i,N) {
		FOR(x,N) D[x]=1LL<<60;
		D[i]=0;
		priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > Q;
		Q.push(make_pair(0,i));
		while(!Q.empty()) {
			pair<int,int> k=Q.top();
			Q.pop();
			int cur=k.second;
			if(k.first != D[cur]) continue;
			
			FOR(j,E[cur].size()) {
				int tar=E[cur][j].second;
				if(D[tar] > D[cur]+E[cur][j].first) {
					D[tar] = D[cur]+E[cur][j].first;
					Q.push(make_pair(D[tar],tar));
				}
			}
		}
		vector<ll> V;
		FOR(x,N) if(x!=i) V.push_back(D[x]/R);
		sort(V.begin(),V.end());
		FOR(j,V.size()) {
			ll t=V[j]*R/T;
			vector<ll>::iterator it=upper_bound(V.begin(),V.end(),t);
			int id=it-V.begin();
			if(id>j) ret+=V.size()-id;
			else ret+=V.size()-id-1;
		}
	}
	cout << ret << endl;
}

まとめ

直前のSRM624もDijkstraだったので、こちらもすぐ思いつけた。