首先可以看出这是一道求最短路的题目，但暴力建图最多n2 条边，所以考虑建图优化

对于p>sqrt(n) 的青蛙可以直接暴力建，最多n*sqrt（n） 条边

对于p<sqrt(n) 的青蛙添加辅助点，枚举这sqrt（n）个长度，每个长度建立n个辅助点前后对应连边，同时向它们可以到达的点以及可以到达它们的点连边

1 #define MAXN 4000010UL 2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6  7 using namespace std; 8  9 int n, m, t, inf, S, T, d[MAXN], dis[MAXN], mp[30010][175];10 bool ins[MAXN];11 12 struct Edge {13     int hou, nt, zhi;14 }sg[MAXN<<2];15 16 void Add(int x, int y, int z) {17     sg[t] = (Edge){y, d[x], z}, d[x] = t ++;18     return;19 }20 21 void Spfa(int x) {22     memset(dis, 0x3f, sizeof(dis));23     inf = dis[0];24     dis[x] = 0;25     queue 
          
            q; q.push(x);26     while(!q.empty()) {27         int op = q.front(); q.pop();28         ins[op] = false;29         for(int i = d[op] ; i != -1 ; i = sg[i].nt) if(dis[sg[i].hou]>dis[op]+sg[i].zhi) {30             dis[sg[i].hou] = dis[op]+sg[i].zhi;31             if(!ins[sg[i].hou]) {32                 ins[sg[i].hou] = true;33                 q.push(sg[i].hou);34             }35         }36     }37     return;38 }39 40 int main() {41     memset(d, -1, sizeof(d));42     scanf("%d%d", &n, &m);43     int blo = (int)sqrt(n), tot = n-1;44     for(int i = 0 ; i < n ; ++ i) {45         for(int j = 1 ; j <= blo ; ++ j) mp[i][j] = ++ tot, Add(tot, i, 0);46     }47     48     for(int i = 0 ; i < n ; ++ i) {49         for(int j = 1 ; j <= blo ; ++ j) {50             if(i+j
           
            =0) Add(mp[i][j], mp[i-j][j], 1);52 }53 }54 for(int i = 0, b, p ; i < m ; ++ i) {55 scanf("%d%d", &b, &p);56 if(i==0) S = b;57 if(i==1) T = b;58 if(p<=blo) Add(b, mp[b][p], 0);59 else {60 for(int j = 1 ; b+j*p < n ; ++ j) Add(b, b+j*p, j);61 for(int j = 1 ; b-j*p >= 0 ; ++ j) Add(b, b-j*p, j);62 }63 }64 Spfa(S);65 if(dis[T]==inf) printf("-1");66 else printf("%d", dis[T]);67 return 0;68 }