結果

問題 No.160 最短経路のうち辞書順最小
ユーザー mikitmikit
提出日時 2020-10-24 15:05:07
言語 Java21
(openjdk 21)
結果
AC  
実行時間 137 ms / 5,000 ms
コード長 9,319 bytes
コンパイル時間 3,199 ms
コンパイル使用メモリ 87,696 KB
実行使用メモリ 54,704 KB
最終ジャッジ日時 2023-09-28 20:26:36
合計ジャッジ時間 7,286 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 58 ms
50,748 KB
testcase_01 AC 59 ms
50,500 KB
testcase_02 AC 59 ms
50,736 KB
testcase_03 AC 62 ms
50,132 KB
testcase_04 AC 93 ms
52,872 KB
testcase_05 AC 118 ms
53,576 KB
testcase_06 AC 137 ms
53,608 KB
testcase_07 AC 75 ms
50,880 KB
testcase_08 AC 78 ms
51,080 KB
testcase_09 AC 75 ms
51,256 KB
testcase_10 AC 76 ms
51,592 KB
testcase_11 AC 80 ms
50,992 KB
testcase_12 AC 80 ms
51,440 KB
testcase_13 AC 75 ms
51,300 KB
testcase_14 AC 72 ms
51,256 KB
testcase_15 AC 71 ms
50,352 KB
testcase_16 AC 77 ms
51,376 KB
testcase_17 AC 71 ms
50,556 KB
testcase_18 AC 74 ms
51,172 KB
testcase_19 AC 77 ms
51,152 KB
testcase_20 AC 77 ms
50,992 KB
testcase_21 AC 70 ms
50,980 KB
testcase_22 AC 71 ms
50,404 KB
testcase_23 AC 79 ms
50,912 KB
testcase_24 AC 83 ms
51,404 KB
testcase_25 AC 75 ms
51,088 KB
testcase_26 AC 74 ms
51,160 KB
testcase_27 AC 65 ms
50,660 KB
testcase_28 AC 111 ms
54,704 KB
testcase_29 AC 62 ms
50,208 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.nio.CharBuffer;
import java.util.PriorityQueue;
import java.io.IOException;
import java.nio.charset.CharsetDecoder;
import java.nio.charset.StandardCharsets;
import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.io.UncheckedIOException;
import java.util.List;
import java.util.AbstractCollection;
import java.nio.charset.Charset;
import java.io.Writer;
import java.util.Comparator;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper reloaded plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner2 in = new LightScanner2(inputStream);
        LightWriter2 out = new LightWriter2(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, LightScanner2 in, LightWriter2 out) {
            int n = in.ints(), m = in.ints(), st = in.ints(), gl = in.ints();
            List<List<TaskD.Edge>> g = new ArrayList<>(n);
            for (int i = 0; i < n; i++) g.add(new ArrayList<>());
            for (int i = 0; i < m; i++) {
                int a = in.ints(), b = in.ints();
                long c = in.longs();
                g.get(b).add(new TaskD.Edge(a, c));
                g.get(a).add(new TaskD.Edge(b, c));
            }
            long[] dist = new long[n];
            int[] from = new int[n];
            Arrays.fill(dist, 1L << 61);
            Arrays.fill(from, -1);
            dist[gl] = 0;
            PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.comparing(i -> dist[i]));
            q.offer(gl);
            while (!q.isEmpty()) {
                int x = q.poll();
                for (TaskD.Edge e : g.get(x)) {
                    long c = dist[x] + e.cost;
                    if (c < dist[e.to]) {
                        dist[e.to] = c;
                        from[e.to] = x;
                        q.offer(e.to);
                    } else if (c == dist[e.to]) {
                        from[e.to] = Math.min(from[e.to], x);
                    }
                }
            }
            if (dist[st] >= (1L << 61)) {
                out.ans(-1).ln();
                return;
            }
            int now = st;
            out.ans(st);
            for (int i = 0; now != gl; i++) {
                now = from[now];
                out.ans(now);
            }
            out.ln();
        }

        private static class Edge {
            int to;
            long cost;

            Edge(int to, long cost) {
                this.to = to;
                this.cost = cost;
            }

        }

    }

    static abstract class LightScannerAdapter implements AutoCloseable {
        public abstract void close();

    }

    static class LightWriter2 implements AutoCloseable {
        private static final int BUF_SIZE = 16 * 1024;
        private final OutputStream out;
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr;
        private boolean autoflush = false;
        private boolean breaked = true;

        public LightWriter2(OutputStream out) {
            this.out = out;
        }

        public LightWriter2(Writer out) {
            this.out = new LightWriter2.WriterOutputStream(out);
        }

        private void allocate(int n) {
            if (ptr + n <= BUF_SIZE) return;
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
            if (BUF_SIZE < n) throw new IllegalArgumentException("Internal buffer exceeded");
        }

        public void close() {
            try {
                out.write(buf, 0, ptr);
                ptr = 0;
                out.flush();
                out.close();
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        private static int countDigits(int l) {
            if (l >= 1000000000L) return 10;
            if (l >= 100000000L) return 9;
            if (l >= 10000000L) return 8;
            if (l >= 1000000L) return 7;
            if (l >= 100000L) return 6;
            if (l >= 10000L) return 5;
            if (l >= 1000L) return 4;
            if (l >= 100L) return 3;
            if (l >= 10L) return 2;
            return 1;
        }

        public LightWriter2 ans(int x) {
            allocate(12);
            if (!breaked) buf[ptr++] = ' ';
            breaked = false;

            if (x < 0) {
                buf[ptr++] = '-';
                x = -x;
            }
            int n = countDigits(x);
            for (int i = ptr + n - 1; ptr <= i; i--) {
                buf[i] = (byte) (x % 10 + '0');
                x /= 10;
            }
            ptr += n;

            return this;
        }

        public LightWriter2 ln() {
            allocate(1);
            buf[ptr++] = '\n';
            breaked = true;
            if (autoflush) {
                try {
                    out.flush();
                } catch (IOException ex) {
                    throw new UncheckedIOException(ex);
                }
            }
            return this;
        }

        private static class WriterOutputStream extends OutputStream {
            final Writer writer;
            final CharsetDecoder decoder;

            WriterOutputStream(Writer writer) {
                this.writer = writer;
                this.decoder = StandardCharsets.UTF_8.newDecoder();
            }

            public void write(int b) throws IOException {
                writer.write(b);
            }

            public void write(byte[] b) throws IOException {
                writer.write(decoder.decode(ByteBuffer.wrap(b)).array());
            }

            public void write(byte[] b, int off, int len) throws IOException {
                writer.write(decoder.decode(ByteBuffer.wrap(b, off, len)).array());
            }

            public void flush() throws IOException {
                writer.flush();
            }

            public void close() throws IOException {
                writer.close();
            }

        }

    }

    static class LightScanner2 extends LightScannerAdapter {
        private static final int BUF_SIZE = 16 * 1024;
        private final InputStream stream;
        private final byte[] buf = new byte[BUF_SIZE];
        private int ptr;
        private int len;

        public LightScanner2(InputStream stream) {
            this.stream = stream;
        }

        private void reload() {
            try {
                ptr = 0;
                len = stream.read(buf);
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        private void load(int n) {
            if (ptr + n <= len) return;
            System.arraycopy(buf, ptr, buf, 0, len - ptr);
            len -= ptr;
            ptr = 0;
            try {
                int r = stream.read(buf, len, BUF_SIZE - len);
                if (r == -1) return;
                len += r;
                if (len != BUF_SIZE) buf[len] = '\n';
            } catch (IOException ex) {
                throw new UncheckedIOException(ex);
            }
        }

        private void skip() {
            while (len != -1) {
                while (ptr < len && isTokenSeparator(buf[ptr])) ptr++;
                if (ptr < len) return;
                reload();
            }
            throw new NoSuchElementException("EOF");
        }

        public int ints() {
            skip();
            load(12);
            int b = buf[ptr++];
            boolean negate;
            if (b == '-') {
                negate = true;
                b = buf[ptr++];
            } else negate = false;
            int x = 0;
            for (; !isTokenSeparator(b); b = buf[ptr++]) {
                if ('0' <= b && b <= '9') x = x * 10 + b - '0';
                else throw new NumberFormatException("Unexpected character '" + ((char) b) + "'");
            }
            return negate ? -x : x;
        }

        public long longs() {
            skip();
            load(20);
            int b = buf[ptr++];
            boolean negate;
            if (b == '-') {
                negate = true;
                b = buf[ptr++];
            } else negate = false;
            long x = 0;
            for (; !isTokenSeparator(b); b = buf[ptr++]) {
                if ('0' <= b && b <= '9') x = x * 10 + b - '0';
                else throw new NumberFormatException("Unexpected character '" + b + "'");
            }
            return negate ? -x : x;
        }

        public void close() {
            try {
                stream.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        private static boolean isTokenSeparator(int b) {
            return b < 33 || 126 < b;
        }

    }
}
0