题目描述

    // 如果使用一维的dis[i], 优先队列保存{u, 槽下标}，槽{-1， 0， 2}下标为0， 1， 2
    // 1层[0花销][槽下标1]->3层[5花销][槽下标2]->2层[9花销][槽下标0]->4层[15花销][槽下标2]
    // 1层[0花销][槽下标1]->3层[5花销][槽下标2]->5层[9花销][槽下标2]->4层[13花销][槽下标0]（这时会更新dis[4]）
    // dijkstra的过程中，dis[4]在到达队列元素{4, 2}和{4, 0}时产生了两个dis[4], 
    // dis[4]会被另一个更小的更新，但是队列中的槽下标却保持不变，导致此后计算cost的过程出错
    // 因此每个楼层dis还需要记录其产生的槽下标

样例

import java.io.*;
import java.util.*;
class Main{
    static int N;
    static int M;
    static int[] C;
    static int[][] dis;
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    static int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception{
        String[] l1 = reader.readLine().split(" ");
        N = Integer.parseInt(l1[0]);
        M = Integer.parseInt(l1[1]);
        C = new int[M];
        String[] l2 = reader.readLine().split(" ");
        int zero = -1;
        for(int i = 0; i < M; i++){
            C[i] = Integer.parseInt(l2[i]);
            if(C[i] == 0) zero = i;
        }
        dis = new int[N + 1][M];//dis[i][j] i为楼层， j为控制槽下标
        for(int i = 1; i <= N; i++) {
            Arrays.fill(dis[i], INF);
        }
        dis[1][zero] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->dis[a[0]][a[1]]-dis[b[0]][b[1]]);
        pq.offer(new int[]{1, zero});
        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int u = cur[0];
            int k = cur[1];
            for(int i = 0; i < M; i++){
                int v = u + C[i];
                if(v < 1) continue;
                if(v > N) break;
                int cost = Math.abs(u - v)*2;
                cost += Math.abs(i - k);
                if(dis[v][i] > dis[u][k] + cost){
                    dis[v][i] = dis[u][k] + cost;
                    pq.offer(new int[]{v, i});
                }
            }
        }
        int ans = INF;
        for(int i = 0; i < M; i++){
            ans = Math.min(ans, dis[N][i]);
        }
        if(ans == INF) ans = -1;
        System.out.println(ans);
    }
}