[APIO2015] 雅加达的摩天楼 【SPFA+卡时+乱搞】

tonyfang posted @ 2015年9月06日 22:11 in APIO with tags c++ OI , 628 阅读

Description

印尼首都雅加达市有N座摩天楼,它们排列成一条直线,我们从左到右依次将它们编号为 0 到N − 1。除了这N座摩天楼外,雅加达市没有其他摩天楼。

有M只叫做“doge”的神秘生物在雅加达市居住,它们的编号依次是 0 到M−1。编号为i的 doge 最初居住于编号为B i 的摩天楼。每只 doge 都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为i的 doge 的跳跃能力为P i (P i > 0)。在一次跳跃中,位于摩天楼b而跳跃能力为p的 doge 可以跳跃到编号为b − p(如果0 ≤ b − p < N)或b + p(如果 0 ≤ b + p < N)的摩天楼。

编号为 0 的 doge 是所有 doge 的首领,它有一条紧急的消息要尽快传送给编号为 1 的 doge。任何一个收到消息的 doge有以下两个选择:

1. 跳跃到其他摩天楼上;

2. 将消息传递给它当前所在的摩天楼上的其他 doge。

请帮助 doge 们计算将消息从 0 号 doge 传递到 1 号 doge 所需要的最少总跳跃步数,或者告诉它们消息永远不可能传递到 1 号 doge。

Input Format

输入的第一行包含两个整数N和M,接下来M行,每行包含两个整数B i 和P i 。

Output Format

输出一行,表示所需要的最少步数。如果消息永远无法传递到 1 号 doge,输出−1。

Sample Input

5 3
0 2
1 1
4 1

Sample Output

5

Hint

【样例解释】

下面是一种步数为 5 的解决方案:

0 号 doge 跳跃到 2 号摩天楼,再跳跃到 4 号摩天楼(2 步)。

0 号 doge 将消息传递给 2 号 doge。

2 号 doge 跳跃到 3 号摩天楼,接着跳跃到 2 号摩天楼,再跳跃到 1 号摩天楼(3 步)。

2 号 doge 将消息传递给 1 号 doge。

【数据规模和约定】

共有五部分数据。所有数据都保证0 ≤ B i < N。

第 1 部分数据占 10 分,数据范围满足: 1 ≤ N ≤ 10, 1 ≤ P i ≤ 10, 2 ≤ M ≤ 3;

第 2 部分数据占 12 分,数据范围满足: 1 ≤ N ≤ 100, 1 ≤ P i ≤ 100, 2 ≤ M ≤2000;

第 3 部分数据占 19 分,数据范围满足:1 ≤ N ≤ 2000, 1 ≤ P i ≤ 2000,2 ≤M ≤ 2000;

第 4 部分数据占 17 分,数据范围满足:1 ≤ N ≤ 2000, 1 ≤ P i ≤ 2000,2 ≤M ≤ 30000;

第 5 部分数据占 42 分,数据范围满足:1 ≤ N ≤ 30000,1 ≤ P i ≤ 30000,2 ≤ M ≤ 30000。

 

 

【题解】

惨烈无比的AC~

好像超过了APIO的限制了。。

就加了一个优化跑SPFA:狗只会跳到有狗的塔上。

然后简单判了个重,直接上,98分~

maya还有2分怎么破!

卡时!卡在SPFA上,发现还是98!建图炸了!!!

这种建图怎么炸?当然用一堆1卡咯!

于是就在建图卡了下时,一堆1的话,最后就是$(b_2-b_1)$,就卡了卡~

过了!!!

哇那一刻好感动!(只是数据弱,其实这样还是容易被卡的,边跑spfa边建图可以卡时过)

 

# include <stdio.h>
# include <queue>
# include <vector>
# include <ctime>
using namespace std;
const int Maxn=800010;
int n,m,b[30010],p[30010],S,T;
vector<int> to[30010], w[30010];
bool havedog[30010];
bool vis[30010];
int d[30010];
queue<int> q;
const int INF=233333333;
inline int read() {
	int x=0,f=1;char c=getchar();
	while(c>'9'||c<'0') {if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
inline void spfa() {
	while(!q.empty()) q.pop();
	for (int i=0;i<=n;++i) d[i]=INF;
	d[S]=0;vis[S]=1;q.push(S);
	while(!q.empty()) {
		if(clock() / double(CLOCKS_PER_SEC) > 0.45) return;
		int top=q.front();q.pop();vis[top]=0;
		for (int i=0;i<to[top].size();++i) {
			int _to=to[top][i];
			if (d[_to]>d[top]+w[top][i]) {
				d[_to]=d[top]+w[top][i];
				if(!vis[_to]) {
					vis[_to]=1;
					q.push(_to);
				}
			}
		}
	}
}
int main() {
	
	n=read(),m=read();
	for (int i=1;i<=m;++i) {
		b[i]=read(),p[i]=read();
		havedog[b[i]]=1;
	}
	b[0]=INF,p[0]=INF;
	bool ff=1;
	for (int i=1;i<=m;++i) {
		if(clock() / double(CLOCKS_PER_SEC) > 0.45) {
			ff=0;
			break;
		}
		int b1=b[i],p1=p[i];
		if(b1==b[i-1]&&p1==p[i-1]&&i>=10)continue;
		for (int j=b1+p1;j<=n;j+=p1) {
			if(!havedog[j]) continue;
			to[b1].push_back(j);
			w[b1].push_back((j-b1)/p1);
		}
		for (int j=b1-p1;j>=0;j-=p1) {
			if(!havedog[j]) continue;
			to[b1].push_back(j);
			w[b1].push_back((b1-j)/p1);
		}
		if(i==1) S=b1;
		if(i==2) T=b1;
	}
	if(ff==0) {
		printf("%d\n",b[2]-b[1]);
		return 0;
	}
	if (S==T) {printf("0\n"); return 0;}
	spfa();
	if(d[T]!=INF) printf("%d\n",d[T]);
	else printf("-1\n");
	return 0;
}
EB reading 说:
2022年8月05日 21:07

Tamil Nadu Electricity Board is the only source of power distribution in Tamil Nadu state. It does provide electricity to every consumer at affordable prices. The electricity processing is quick, and it gets install within short of consumers register with their department. Tamil Nadu Electricity Board is the only source of power distribution in Tamil Nadu state. EB reading It does provide electricity to every consumer at affordable prices.Tamil Nadu Generation and Distribution Corporation Limited is under the TamilNadu government, decide the unit rate applied on electricity usage. This price is the same for everyone around the state and the meter billing is all considered to be similar.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter