#749457 (Java) No.1602 With Animals into Institute 2

• 問題: No.1602 With Animals into Institute 2
• ユーザー: Yu_212
• 提出日時: 2022-03-28 22:03:07
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 2,822 ms / 4,000 ms
• コード長: 10,714 bytes
• コンパイル時間: 3,589 ms
• コンパイル使用メモリ: 100,884 KB
• 実行使用メモリ: 119,740 KB
• 最終ジャッジ日時: 2024-11-07 12:44:32
• 合計ジャッジ時間: 42,418 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 36

ソースコード

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.function.BinaryOperator;
import java.util.function.IntUnaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.Collectors;

public class Main {
    static In in = new In();
    static Out out = new Out();
    static final long inf = 0x1fffffffffffffffL;
    static final int iinf = 0x3fffffff;
    static final double eps = 1e-9;
    static long mod = 1000000007;

    void solve() {
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        ShortestNonzeroPath.Group<Integer> group = new ShortestNonzeroPath.Group<>(0, (a, b) -> a ^ b);
        ShortestNonzeroPath<Integer> snp = new ShortestNonzeroPath<>(n, group);
        for (int i = 0; i < m; i++) {
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            long c = in.nextLong();
            char[] x = in.nextCharArray();
            int label = 0;
            for (int j = 0; j < k; j++) {
                label |= (x[j] - '0') << j;
            }
            snp.addEdge(a, b, c, label);
            snp.addEdge(b, a, c, label);
        }
        snp.solve(n - 1);
        for (int i = 0; i < n - 1; i++) {
            out.println(snp.dist(i) == inf ? -1 : snp.dist(i));
        }
    }

    public static void main(String... args) {
        new Main().solve();
        out.flush();
    }
}

class ShortestNonzeroPath<T> {
    private final int n;
    private final List<List<Edge>> edges;
    private final Group<T> group;
    private final int[] uf;
    private final long[] nonzeroDist;

    public ShortestNonzeroPath(int n, Group<T> group) {
        this.n = n;
        this.edges = new ArrayList<>();
        this.group = group;
        this.uf = new int[n];
        this.nonzeroDist = new long[n];
        for (int i = 0; i < n; i++) {
            uf[i] = i;
            nonzeroDist[i] = Main.inf;
            edges.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v, long len, T label) {
        edges.get(u).add(new Edge(u, v, len, label));
    }

    private int root(int x) {
        while (x != uf[x]) {
            x = uf[x] = uf[uf[x]];
        }
        return x;
    }

    public void solve(int s) {
        long[] dist = new long[n];
        int[] depth = new int[n];
        int[] parent = new int[n];
        List<T> label = new ArrayList<>(Collections.nCopies(n, group.identity));
        Arrays.fill(dist, Main.inf);
        Arrays.fill(depth, -1);
        Arrays.fill(parent, -1);
        PriorityQueue<Pair> queue = new PriorityQueue<>();
        dist[s] = 0;
        depth[s] = 0;
        queue.add(new Pair(null, 0));
        while (!queue.isEmpty()) {
            Pair pair = queue.remove();
            int u = pair.edge == null ? s : pair.edge.to;
            if (dist[u] < pair.len) {
                continue;
            }
            for (Edge edge : edges.get(u)) {
                int v = edge.to;
                if (dist[v] > dist[u] + edge.len) {
                    dist[v] = dist[u] + edge.len;
                    depth[v] = depth[u] + 1;
                    parent[v] = u;
                    label.set(v, group.operator.apply(label.get(u), edge.label));
                    queue.add(new Pair(edge, dist[edge.to]));
                }
            }
        }
        for (int u = 0; u < n; u++) {
            if (dist[u] == Main.inf) {
                continue;
            }
            for (Edge edge : edges.get(u)) {
                int v = edge.to;
                if (u < v && !Objects.equals(group.operator.apply(label.get(u), edge.label), label.get(v))) {
                    long len = dist[u] + dist[v] + edge.len;
                    queue.add(new Pair(edge, len));
                }
            }
        }
        while (!queue.isEmpty()) {
            Pair pair = queue.remove();
            int u = root(pair.edge.from);
            int v = root(pair.edge.to);
            List<Integer> bs = new ArrayList<>();
            while (u != v) {
                if (depth[u] > depth[v]) {
                    bs.add(u);
                    u = root(parent[u]);
                } else {
                    bs.add(v);
                    v = root(parent[v]);
                }
            }
            for (int x : bs) {
                uf[x] = u;
                nonzeroDist[x] = pair.len - dist[x];
                for (Edge edge : edges.get(x)) {
                    if (Objects.equals(group.operator.apply(label.get(x), edge.label), label.get(edge.to))) {
                        queue.add(new Pair(edge, nonzeroDist[x] + dist[edge.to] + edge.len));
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (!Objects.equals(label.get(i), group.identity) && dist[i] < nonzeroDist[i]) {
                nonzeroDist[i] = dist[i];
            }
        }
    }

    public long dist(int v) {
        return nonzeroDist[v];
    }

    private class Pair implements Comparable<Pair> {
        private final Edge edge;
        private final long len;

        private Pair(Edge edge, long len) {
            this.edge = edge;
            this.len = len;
        }

        @Override
        public int compareTo(Pair p) {
            return Long.compare(len, p.len);
        }
    }

    private class Edge {
        private final int from;
        private final int to;
        private final long len;
        private final T label;

        private Edge(int from, int to, long len, T label) {
            this.from = from;
            this.to = to;
            this.len = len;
            this.label = label;
        }
    }

    static class Group<T> {
        private final T identity;
        private final BinaryOperator<T> operator;

        public Group(T identity, BinaryOperator<T> operator) {
            this.identity = identity;
            this.operator = operator;
        }
    }
}

class In {
    private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 0x10000);
    private StringTokenizer tokenizer;

    String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
        } catch (IOException ignored) {
        }
        return tokenizer.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    char[] nextCharArray() {
        return next().toCharArray();
    }

    String[] nextStringArray(int n) {
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = next();
        }
        return s;
    }

    char[][] nextCharGrid(int n, int m) {
        char[][] a = new char[n][m];
        for (int i = 0; i < n; i++) {
            a[i] = next().toCharArray();
        }
        return a;
    }

    int[] nextIntArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextInt();
        }
        return a;
    }

    int[] nextIntArray(int n, IntUnaryOperator op) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsInt(nextInt());
        }
        return a;
    }

    int[][] nextIntMatrix(int h, int w) {
        int[][] a = new int[h][w];
        for (int i = 0; i < h; i++) {
            a[i] = nextIntArray(w);
        }
        return a;
    }

    long[] nextLongArray(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = nextLong();
        }
        return a;
    }

    long[] nextLongArray(int n, LongUnaryOperator op) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = op.applyAsLong(nextLong());
        }
        return a;
    }

    long[][] nextLongMatrix(int h, int w) {
        long[][] a = new long[h][w];
        for (int i = 0; i < h; i++) {
            a[i] = nextLongArray(w);
        }
        return a;
    }

    List<List<Integer>> nextEdges(int n, int m, boolean directed) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            res.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int u = nextInt() - 1;
            int v = nextInt() - 1;
            res.get(u).add(v);
            if (!directed) {
                res.get(v).add(u);
            }
        }
        return res;
    }
}

class Out {
    private final PrintWriter out = new PrintWriter(System.out);
    boolean autoFlush = false;

    void println(Object... args) {
        if (args == null || args.getClass() != Object[].class) {
            args = new Object[] {args};
        }
        out.println(Arrays.stream(args).map(obj -> {
            Class<?> clazz = obj == null ? null : obj.getClass();
            return clazz == Double.class ? String.format("%.10f", obj) :
                   clazz == byte[].class ? Arrays.toString((byte[])obj) :
                   clazz == short[].class ? Arrays.toString((short[])obj) :
                   clazz == int[].class ? Arrays.toString((int[])obj) :
                   clazz == long[].class ? Arrays.toString((long[])obj) :
                   clazz == char[].class ? Arrays.toString((char[])obj) :
                   clazz == float[].class ? Arrays.toString((float[])obj) :
                   clazz == double[].class ? Arrays.toString((double[])obj) :
                   clazz == boolean[].class ? Arrays.toString((boolean[])obj) :
                   obj instanceof Object[] ? Arrays.deepToString((Object[])obj) :
                   String.valueOf(obj);
        }).collect(Collectors.joining(" ")));
        if (autoFlush) {
            out.flush();
        }
    }

    void println(char[] s) {
        out.println(String.valueOf(s));
        if (autoFlush) {
            out.flush();
        }
    }

    void println(int[] a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (int i : a) {
            joiner.add(Integer.toString(i));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    void println(long[] a) {
        StringJoiner joiner = new StringJoiner(" ");
        for (long i : a) {
            joiner.add(Long.toString(i));
        }
        out.println(joiner);
        if (autoFlush) {
            out.flush();
        }
    }

    void flush() {
        out.flush();
    }
}