本文最后更新于:2020年4月11日 下午

问题描述

  • 给出了具有$N$个顶点的无向边距的连通图。

  • 在这里,兔子以速度$R$移动,乌龟以速度$T$移动。

  • 在$N$个顶点的三个元素($A$,$B$,$C$)中,求乌龟从$C$移到$A$的速度比兔子从$B$移到$A$的速度更快的($A$,$B$,$C$)组合的数量。

问题分析

我们可以看目标点A。

对于A ,通过Dijkstra方法计算到每个顶点的距离。

接下来,在循环C之后,确定从B到A的距离大于R / T乘以C到A的对象的数量。

末尾B的计数可以通过测量方法来执行,或者可以通过如下所述的upper_bound来处理。

Dijkstra一次是$O((N + M)logN)$,而C和B的计数是$O(NlogN)$。

核心部分伪$Code$


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;
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解 AT908 【辞書式順序ふたたび】 上一篇
题解 AT1299 【偶然ジェネレータ】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。