[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;
}
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.
2022年9月17日 01:31
Urdu is one of the main languages in the state, and this is the first language for Urdu Medium students, there are fewer schools are working in all districts of the state, all the applicable students also can download AP SSC Urdu Model Paper 2023 Pdf in chapter wise for all lessons of the course, AP SSC Urdu Question Paper download, and practice the Ibtedai Question bank to get better rank in all exams conducted by BSEAP. Urdu is one of the main languages in the state, and this is the first language for Urdu Medium students, there are fewer schools are working in all districts of the state, all the applicable students also can download AP SSC Urdu Model Paper 2023 Pdf in chapter wise for all lessons of the course.
2023年2月08日 16:22
BSNL is installing Bharat Net a country-wide fiber optic cable for internet connectivity in many of the panchayats, and on the other hand, ISP brought the same fibernet technology to your doorstep directly and through TIPs. Bharat Fiber Telecom Infrastructure Providers (TIPs) with new BSNL Fiber plans covering many isolated pockets in all BSNL circles of the country for 50Mbps to 300 Mbps internet speed on providing with BSNL Fiber Plans along with FREE ONT as per the possibility.
2023年7月12日 00:23
Zeus Network provides a dedicated Zeus free trial. Sadly, Zeus does not provide a Zeus free trial period before the membership. The Zeus Network, including documentaries, drama series and reality shows. www.thezeusnetwork.com/activate code firestick Once after downloading, open the application, and “activate Zeus Network” at “thezeusnetwork.com/activate” in search of the available content. Zeus Network without a connecting TV broadcasting service provider the Zeus Network app is available on popular streaming devices.
2024年1月06日 17:02
JNANABHUMI AP provides all the latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who are passionate about providing engaging content that is accurate, interesting, and worthy to read. We are more like a web community where you can find different information, resources, and topics on day-to-day incidents or news. We provide you with the finest web content on each topic possible with the help of the editorial and content team.