分块+最短路
我们把一个(有doge的)点连向所有它能到达的所有点，这样就是一个最短路问题。考虑优化建图，用分块。
如果 p 大于n‾√就直接连。小于 n‾√ 的情况？其实有一个性质，对于一系列有相同 p 的点i<j<k，如果 i 能到达k， j 能到达k，那只要连上 (i,j) 和 (j,k) 而不连 (i,k) 即可。也就是说在 p 相同的情况下，一个点只要有一条入边。
这样总边数O(nn‾√)，跑个dijkstra就行了。
然后在UOJ上交了半天，在Extra Test 31上一直TLE，死活卡不过去。跑去BZOJ交，过了。跑回UOJ再交，突然就也过了？？？
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define N 30005 #define S 205 using namespace std; namespace runzhe2000 { int n, m, s, t, ecnt, lim, last[N], vis[N], dis[N], inf, have[S][N]; struct edge{int next, to, val;}e[N*S<<1]; int read() { int r = 0; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()); for(; c >='0' && c <='9'; r = r * 10 + c - '0', c = getchar()); return r; } void addedge(int a, int b, int c) { e[++ecnt] = (edge){last[a], b, c}; last[a] = ecnt; } struct data { int id, dis; bool operator < (const data &that) const {return dis < that.dis;} }h[N*S<<1]; int tot = 0; void heap_ins(data x) { h[++tot] = x; for(int i = tot, j = i >> 1; j; i = j, j >>= 1) if(h[i] < h[j]) swap(h[j], h[i]); else break; } void heap_pop() { h[1] = h[tot--]; for(int i = 1, j = 2; j <= tot; i = j, j <<= 1) { if(h[j|1] < h[j] && j < tot) j |= 1; if(h[j] < h[i]) swap(h[j], h[i]); else break; } } void dijkstra() { memset(dis, 63, sizeof(dis)); inf = dis[0]; heap_ins((data){s, dis[s] = 0}); for(; tot; ) { int x = h[1].id; heap_pop(); if(vis[x]) continue; vis[x] = 1; for(int i = last[x]; i; i = e[i].next) { int y = e[i].to; if(dis[x] + e[i].val < dis[y]) { dis[y] = dis[x] + e[i].val; heap_ins((data){y, dis[y]}); } } } } void main() { n = read(), m = read(); lim = sqrt((double)(n+1)); for(int i = 1; i <= m; i++) { int b = read(), p = read(); if(i == 1) s = b; if(i == 2) t = b; if(p > lim) { for(int j = b+p, s = 1; j < n; j += p, s++) addedge(b, j, s); for(int j = b-p, s = 1; j >= 0; j -= p, s++) addedge(b, j, s); } else have[p][b] = 1; } for(int j = 1; j <= lim; j++) { int *hj = have[j]; for(int i = 0; i < n; i++)if(hj[i]) { for(int k = i+j, s = 1; k < n; k += j, s++){addedge(i, k, s); if(hj[k])break;} for(int k = i-j, s = 1; k >= 0; k -= j, s++){addedge(i, k, s); if(hj[k])break;} } } dijkstra();printf("%d\n",dis[t]!=inf?dis[t]:-1); } } int main() { runzhe2000::main(); }