题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4070
数据生成器:http://paste.ubuntu.com/23101297/
这个题目,第一眼看就是最短路
然而O(n^2)条边真的是过不了
于是我们分类讨论,将p小于sqrt(n)的边全部建出来,p大于的暴力建
貌似叫分层图?还是看这里吧:http://blog.csdn.net/aarongzk/article/details/51195437?hmsr=toutiao.io
然而随便出一个数据就可以把这个做法搞死QAQ
管他的,卡过就好
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#include<queue>
#include<ctime>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define NUM(p,f) (((p)-1)*(gap+1)+(f))
using namespace std;
const int N = 30005*110;
const int M = 30005*550;
const int INF = 0x3f;
const int inf = 0x3f3f3f3f;
struct Edge{int to,nxt,cost;}e[M];
int head[N],dis[N],inq[N],S,T,n,m,gap;
queue<int> que;
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}
inline void AddEdge(int u, int v, int c){
static int TT = 0; e[++TT].cost = c;
e[TT].to = v; e[TT].nxt = head[u]; head[u] = TT;
}
inline int SPFA(int u, int v){
memset(dis,INF,sizeof(dis));
dis[u] = 0; que.push(u); inq[u] = 1;
while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
for (int i=head[w];i;i=e[i].nxt) if (dis[w]+e[i].cost < dis[e[i].to]) {
int to = e[i].to;
dis[to] = dis[w] + e[i].cost;
if (!inq[to]) que.push(to), inq[to] = 1;
}
}
if (dis[v] == inf) return -1;
else return dis[v];
}
int main(){
n = read(); m = read(); gap = max(1,min(100,(int)sqrt(n)));
for (int i=1;i<=n;i++) for (int j=1;j<=gap;j++) AddEdge(NUM(i,j),NUM(i,0),0);
for (int i=1;i<n;i++) for (int j=1;j<=gap;j++) if (i+j <= n) AddEdge(NUM(i,j),NUM(i+j,j),1); else break;
for (int i=2;i<=n;i++) for (int j=1;j<=gap;j++) if (i-j > 0) AddEdge(NUM(i,j),NUM(i-j,j),1); else break;
for (int i=1,pos,rag;i<=m;i++) {
pos = read()+1; rag = read();
if (i == 1) S = NUM(pos,0); if (i == 2) T = NUM(pos,0);
if (rag > gap) {
for (int j=pos+rag,t=1;j<=n;j+=rag,t++) AddEdge(NUM(pos,0),NUM(j,0),t);
for (int j=pos-rag,t=1;j>0;j-=rag,t++) AddEdge(NUM(pos,0),NUM(j,0),t);
} else AddEdge(NUM(pos,0),NUM(pos,rag),0);
} printf("%d\n",SPFA(S,T));
return 0;
}