[题目链接]

        https://www.lydsy.com/JudgeOnline/problem.php?id=4070

[算法]

         考虑将每个"Doge"向其所能到达的楼连边

         直接SPFA求单源最短路可以获得57分

         那么 ， 怎样拿到满分呢？

         我们发现这张图的边的数量达到了NM的数量级

         考虑分块 ， 将每个点拆成SQRT(N)个点

         将每个Pi <= SQRT(N)的点向(Bi , Pi)连边 ， 这样的边不会超过N * SQRT(N)条

         将每个Pi > SQRT(N)的点向其所能到达的所有点连边 ， 这样的边不会超过NlogN条

         时间复杂度 : O(N ^ 2) , 实际远不能达到这个上限

[代码]

#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;typedef unsigned long long ull;const int inf = 1e9;const int N = 6000050;struct edge{ int to , w , nxt;} e[15000005];int n , m , block , tot , S , T;int head[N] , dist[N];bool inq[N];template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }template <typename T> inline void read(T &x){ T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - ‘0‘; x *= f;}inline int id(int x , int y){ return y * n + x;}inline void addedge(int u , int v , int w){ ++tot; e[tot] = (edge){v , w , head[u]}; head[u] = tot;}inline int SPFA(){ queue< int > q; q.push(S); memset(dist , 0x3f , sizeof(dist)); dist[S] = 0; inq[S] = true; while (!q.empty()) { int cur = q.front(); q.pop(); inq[cur] = false; for (int i = head[cur]; i; i = e[i].nxt) { int v = e[i].to , w = e[i].w; if (dist[cur] + w < dist[v]) { dist[v] = dist[cur] + w; if (!inq[v]) { inq[v] = true; q.push(v); } } } } return dist[T] != 0x3f3f3f3f ? dist[T] : -1;}int main(){ read(n); read(m); block = min((int)sqrt(n) , 100); for (int i = 1; i <= block; ++i) { for (int j = i; j < n; ++j) { addedge(id(j , i) , id(j - i , i) , 1); addedge(id(j - i , i) , id(j , i) , 1); } for (int j = 0; j < n; ++j) addedge(id(j , i) , id(j , 0) , 0); } for (int k = 1; k <= m; ++k) { int Bi , Pi; read(Bi); read(Pi); if (Pi <= block) addedge(id(Bi , 0) , id(Bi , Pi) , 0); else { for (int i = Bi + Pi; i < n; i += Pi) addedge(id(Bi , 0) , id(i , 0) , (i - Bi) / Pi); for (int i = Bi - Pi; i >= 0; i -= Pi) addedge(id(Bi , 0) , id(i , 0) , (Bi - i) / Pi); } if (k == 1) S = id(Bi , 0); if (k == 2) T = id(Bi , 0); } printf("%d\n" , SPFA()); return 0; }