結果
| 問題 | No.807 umg tours |
| ユーザー |
 neko_the_shadow
|
| 提出日時 | 2020-10-24 10:48:16 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,990 bytes |
| コンパイル時間 | 3,587 ms |
| コンパイル使用メモリ | 88,452 KB |
| 実行使用メモリ | 128,000 KB |
| 最終ジャッジ日時 | 2023-09-28 20:13:51 |
| 合計ジャッジ時間 | 29,036 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 93 ms
51,864 KB |
| testcase_01 | AC | 92 ms
51,712 KB |
| testcase_02 | AC | 94 ms
51,956 KB |
| testcase_03 | AC | 95 ms
52,088 KB |
| testcase_04 | AC | 87 ms
51,848 KB |
| testcase_05 | AC | 89 ms
51,416 KB |
| testcase_06 | AC | 94 ms
51,664 KB |
| testcase_07 | AC | 91 ms
51,484 KB |
| testcase_08 | AC | 78 ms
51,868 KB |
| testcase_09 | AC | 82 ms
51,788 KB |
| testcase_10 | AC | 82 ms
51,512 KB |
| testcase_11 | AC | 1,031 ms
90,968 KB |
| testcase_12 | AC | 1,329 ms
98,664 KB |
| testcase_13 | AC | 1,314 ms
103,592 KB |
| testcase_14 | AC | 860 ms
85,516 KB |
| testcase_15 | AC | 703 ms
75,272 KB |
| testcase_16 | AC | 1,386 ms
107,184 KB |
| testcase_17 | AC | 1,629 ms
127,724 KB |
| testcase_18 | AC | 1,588 ms
128,000 KB |
| testcase_19 | AC | 1,491 ms
113,040 KB |
| testcase_20 | AC | 1,033 ms
98,468 KB |
| testcase_21 | AC | 1,121 ms
100,208 KB |
| testcase_22 | AC | 688 ms
72,848 KB |
| testcase_23 | AC | 563 ms
66,440 KB |
| testcase_24 | TLE | - |
| testcase_25 | -- | - |
ソースコード
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;
}
@Override
public 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();
}
}
}