D dijkstra做法

D-清楚姐姐跳格子_牛客周赛 Round 54 (nowcoder.com)

清楚正在玩跳格子游戏。地上有 n 个格子，清楚一开始在 1 号格子，目标是 n 号格子。

第 个格子上有一个数字 ，清楚在这个格子上可以往左右两边选一个方向，然后选择 的一个正整数因子作为长度，进行一次跳跃，但是不可以跳出边界。 请问清楚最少跳多少步，就可以到达 号格子。

最短路

对于一个格子能跳到的地方是固定的，那么整个跳跃路线就是一张图，所以可以用dijkstra来求解最短路。

对于每个数我们求解他的因数距离是哪些格子并不好操作，我们反过来枚举格子距离判断是否是他的因数。

然后进行dijkstra的流程求解即可。

import java.io.*;
import java.util.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static int n, d[];
    static long a[];
    static boolean st[];
    public static void solve(){
        n = sc.nextInt();
        a = new long[n + 1];
        d = new int[n + 1];
        st = new boolean[n + 1];
        for(int i = 1; i <= n; i ++) a[i] = sc.nextLong();
        Arrays.fill(d, (int)1e9);
        d[1] = 0;
        for(int i = 0; i < n; i ++){
            int t = -1;
            for(int j = 1; j <= n; j ++){
                if(!st[j] && (t == -1 || d[j] < d[t])) t = j;
            }
            st[t] = true;
            for(int j = (int) Math.max(0, t - a[t]); j <= Math.min(n, t + a[t]); j ++){
                if(!st[j] && a[t] % Math.abs(j - t) == 0) d[j] = Math.min(d[j], d[t] + 1);
            }
        }
        pw.println(d[n]);
    }
    public static void main(String[] args) throws IOException {     
        solve();
        pw.flush();pw.close();
    }
}