提出 #69142074

---

ソースコード 拡げる

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {

    record ParetoEntry(long fuel, long weight) {
    }

    record State(long fuel, long weight, int vertex) {
    }

    public static void main(String[] args) throws Exception {
        BufferedReader bu = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String[] s = bu.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        int[] w = new int[n];
        s = bu.readLine().split(" ");
        for (int i = 0; i < n; i++) w[i] = Integer.parseInt(s[i]);
        ArrayList<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            s = bu.readLine().split(" ");
            int u = Integer.parseInt(s[0]) - 1, v = Integer.parseInt(s[1]) - 1;
            adj[u].add(v);
            adj[v].add(u);
        }
        ArrayList<ParetoEntry>[] minCosts = new ArrayList[n];
        for (int i = 0; i < n; i++) minCosts[i] = new ArrayList<>();
        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingLong(State::fuel));
        long initialW = w[0];
        minCosts[0].add(new ParetoEntry(0, initialW));
        pq.add(new State(0, initialW, 0));
        while (!pq.isEmpty()) {
            State cur = pq.poll();
            long curFuel = cur.fuel(), curWeight = cur.weight();
            int u = cur.vertex();
            for (int v : adj[u]) {
                long newFuel = curFuel + curWeight, newWeight = curWeight + w[v];
                if (!isDominated(minCosts[v], newFuel, newWeight)) {
                    addAndPrune(minCosts[v], newFuel, newWeight);
                    pq.add(new State(newFuel, newWeight, v));
                }
            }
        }
        for (int i = 0; i < n; i++) {
            long minFuel = Long.MAX_VALUE;
            for (ParetoEntry entry : minCosts[i]) minFuel = Math.min(minFuel, entry.fuel());
            sb.append(minFuel + "\n");
        }
        System.out.print(sb);
    }

    private static void addAndPrune(ArrayList<ParetoEntry> minCost, long newFuel, long newWeight) {
        minCost.removeIf(entry -> newFuel <= entry.fuel() && newWeight <= entry.weight());
        minCost.add(new ParetoEntry(newFuel, newWeight));
    }

    private static boolean isDominated(ArrayList<ParetoEntry> minCost, long curFuel, long curWeight) {
        for (ParetoEntry entry : minCost) if (entry.fuel() <= curFuel && entry.weight() <= curWeight) return true;
        return false;
    }
}

提出情報

コンパイルエラー

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

ジャッジ結果