题目传送门: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; }
Rather interesting looking onward to coming back.|