[APIO2015] 雅加达的摩天楼 【SPFA+卡时+乱搞】
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; }