結果
| 問題 | No.807 umg tours |
| ユーザー |
 neko_the_shadow
|
| 提出日時 | 2020-10-24 10:48:16 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,990 bytes |
| コンパイル時間 | 2,955 ms |
| コンパイル使用メモリ | 100,220 KB |
| 実行使用メモリ | 111,264 KB |
| 最終ジャッジ日時 | 2024-07-21 15:01:04 |
| 合計ジャッジ時間 | 25,074 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 24 TLE * 1 -- * 1 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.io.UncheckedIOException;import java.lang.reflect.Array;import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Objects;import java.util.stream.Collectors;import java.util.stream.IntStream;public class Main {public void exec() {int n = stdin.nextInt();int m = stdin.nextInt();Dijkstra2 dijkstra2 = new Dijkstra2(n);for (int i = 0; i < m; i++) {int a = stdin.nextInt() - 1;int b = stdin.nextInt() - 1;long c = stdin.nextLong();dijkstra2.add(a, b, c);dijkstra2.add(b, a, c);}long[] result = dijkstra2.run(0);for (int i = 0; i < n; i++) {stdout.println(result[i]);}}public class Dijkstra2 {private int n;private Map<Integer, List<Edge>> edges;public Dijkstra2(int n) {this.n = n;this.edges = new HashMap<>();}public void add(int from, int to, long cost) {this.edges.computeIfAbsent(from, unused -> new ArrayList<>()).add(new Edge(to, cost));}public long[] run(int start) {long[] score1 = new long[n];long[] score2 = new long[n];Arrays.fill(score1, Long.MAX_VALUE);Arrays.fill(score2, Long.MAX_VALUE);score1[start] = 0;score2[start] = 0;HeapQ<Tuple> q = new HeapQ<>();q.push(0, new Tuple(start, 0, false));q.push(0, new Tuple(start, 0, true));while (!q.isEmpty()) {Tuple t = q.pop();if (!edges.containsKey(t.current)) continue;for (Edge edge : edges.get(t.current)) {if (t.used) {if (t.cost + edge.cost < score2[edge.next]) {score2[edge.next] = t.cost + edge.cost;q.push(score2[edge.next], new Tuple(edge.next, score2[edge.next], true));}} else {if (t.cost + edge.cost < score1[edge.next]) {score1[edge.next] = t.cost + edge.cost;q.push( score1[edge.next], new Tuple(edge.next, score1[edge.next], false));}if (t.cost < score2[edge.next]) {score2[edge.next] = t.cost;q.push(score2[edge.next], new Tuple(edge.next, score2[edge.next], true));}}}}return IntStream.range(0, n).mapToLong(i -> score1[i]+score2[i]).toArray();}private class HeapQ<T> {private ElementList<T> heapq;public HeapQ() {this.heapq = new ElementList<>();}public void push(long x, T t) {this.heapq.add(new Element(x, t));int n = heapq.size() - 1;while (n > 1) {if (heapq.get(n/2).x < heapq.get(n).x) break;Element<T> e1 = heapq.get(n/2);Element<T> e2 = heapq.get(n);heapq.set(n/2, e2);heapq.set(n, e1);n/=2;}}public T pop() {Element<T> ans = heapq.pop();int n = 1;while (n < heapq.size()) {if (n*2 > heapq.size()) break;int m;if (heapq.size() <= n*2+1) {m = n*2;} else {if (heapq.get(n*2).x < heapq.get(n*2+1).x) {m = n*2;} else {m = n*2+1;}}if (heapq.get(n).x < heapq.get(m).x) break;Element<T> e1 = heapq.get(n);Element<T> e2 = heapq.get(m);heapq.set(n, e2);heapq.set(m, e1);n = m;}return ans.t;}public boolean isEmpty() {return heapq.size() == 1;}private class ElementList<T> {private List<Element<T>> list;private int size;public ElementList() {this.list = new ArrayList<>();this.list.add(null);this.size = 1;}public int size() {return this.size;}public Element<T> get(int i) {return list.get(i);}public Element<T> set(int i, Element<T> e) {return list.set(i, e);}public void add(Element<T> e) {if (size == list.size()) {list.add(e);} else {list.set(size, e);}size++;}public Element<T> pop() {Element<T> e = list.get(1);list.set(1, list.get(size-1));size--;return e;}}private class Element<T> {private long x;private T t;public Element(long x, T t) {this.x = x;this.t = t;}}}private class Edge {private int next;private long cost;public Edge(int next, long cost) {this.next = next;this.cost = cost;}}private class Tuple implements Comparable<Tuple>{private int current;private long cost;private boolean used;public Tuple(int current, long cost, boolean used) {this.current = current;this.cost = cost;this.used = used;}@Overridepublic int compareTo(Tuple other) {return Long.compare(this.cost, other.cost);}}}private static final Stdin stdin = new Stdin(System.in);private static final Stdout stdout = new Stdout();public static void main(String[] args) {try {new Main().exec();} finally {stdout.flush();}}public static class Stdin {private InputStream in;private byte[] buf;private int ptr;private int len;public Stdin(InputStream in) {this.in = in;this.buf = new byte[1024];this.ptr = 0;this.len = 0;}public String nextString() {StringBuilder sb = new StringBuilder();byte b;while ((b = read()) != -1) {sb.appendCodePoint(b);}return sb.toString();}public int nextInt() {return (int)nextLong();}public double nextDouble() {return Double.parseDouble(nextString());}public long nextLong() {boolean negative = false;int x = 0;byte b = read();if (b == '-') {negative = true;} else {x += b-'0';}while ((b=read()) != -1) {x *= 10;x += b-'0';}return negative ? -x : x;}private byte read() {byte b = readByte();if (b == '\r') {readByte(); // LFを読み飛ばすreturn -1;} else if (b == '\n' || b == ' ') {return -1;} else {return b;}}private byte readByte(){if (len == ptr) {try {ptr = 0;len = in.read(buf);if (len == -1) return -1;} catch (IOException e) {throw new UncheckedIOException(e);}}return buf[ptr++];}public String[] nextStringArray(int n) {String[] a = new String[n];for (int i = 0; i < n; i++) a[i] = nextString();return a;}public int[] nextIntArray(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = nextInt();return a;}public double[] nextDoubleArray(int n) {double[] a = new double[n];for (int i = 0; i < n; i++) a[i] = nextDouble();return a;}public long[] nextLongArray(int n) {long[] a = new long[n];for (int i = 0; i < n; i++) a[i] = nextLong();return a;}}public static class Stdout {private PrintWriter stdout;public Stdout() {stdout = new PrintWriter(System.out, false);}public void printf(String format, Object ... args) {String line = String.format(format, args);if (line.endsWith(System.lineSeparator())) {stdout.print(line);} else {stdout.println(line);}}public void println(Object ... objs) {String line = Arrays.stream(objs).map(Objects::toString).collect(Collectors.joining(" "));stdout.println(line);}public void printDebug(Object ... objs) {String line = Arrays.stream(objs).map(this::deepToString).collect(Collectors.joining(" "));stdout.printf("DEBUG: %s%n", line);stdout.flush();}private String deepToString(Object o) {if (o == null) {return "null";}// 配列の場合if (o.getClass().isArray()) {int len = Array.getLength(o);String[] tokens = new String[len];for (int i = 0; i < len; i++) {tokens[i] = deepToString(Array.get(o, i));}return "{" + String.join(",", tokens) + "}";}return Objects.toString(o);}private void flush() {stdout.flush();}}}