結果
| 問題 | No.807 umg tours |
| ユーザー |
 neko_the_shadow
|
| 提出日時 | 2020-10-23 15:27:10 |
| 言語 | Java (openjdk 23) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 7,041 bytes |
| コンパイル時間 | 3,267 ms |
| コンパイル使用メモリ | 86,788 KB |
| 実行使用メモリ | 765,200 KB |
| 最終ジャッジ日時 | 2024-07-21 10:05:51 |
| 合計ジャッジ時間 | 19,088 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 11 MLE * 15 |
ソースコード
import java.io.BufferedReader;import java.io.EOFException;import java.io.IOException;import java.io.InputStreamReader;import java.io.PrintWriter;import java.io.UncheckedIOException;import java.lang.reflect.Array;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Deque;import java.util.Objects;import java.util.PriorityQueue;import java.util.regex.Pattern;import java.util.stream.Collectors;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[0][i] + result[1][i]);}}public class Dijkstra2 {private int n;private long[][] cost;public Dijkstra2(int n) {this.n = n;this.cost = new long[n][n];for (long[] row : this.cost) {Arrays.fill(row, -1);}}public void add(int from, int to, long cost) {this.cost[from][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;PriorityQueue<Tuple> q = new PriorityQueue<>();q.add(new Tuple(start, 0, false));q.add(new Tuple(start, 0, true));while (!q.isEmpty()) {Tuple t = q.remove();for (int next = 0; next < n; next++) {if (this.cost[t.current][next] == -1) continue;if (t.used) {if (t.cost + cost[t.current][next] < score2[next]) {score2[next] = t.cost + cost[t.current][next];q.add(new Tuple(next, score2[next], true));}} else {if (t.cost + cost[t.current][next] < score1[next]) {score1[next] = t.cost + cost[t.current][next];q.add(new Tuple(next, score1[next], false));}if (t.cost < score2[next]) {score2[next] = t.cost;q.add(new Tuple(next, score2[next], true));}}}}return new long[][] {score1, score2};}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();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 BufferedReader stdin;private Deque<String> tokens;private Pattern delim;public Stdin() {stdin = new BufferedReader(new InputStreamReader(System.in));tokens = new ArrayDeque<>();delim = Pattern.compile(" ");}public String nextString() {try {if (tokens.isEmpty()) {String line = stdin.readLine();if (line == null) {throw new UncheckedIOException(new EOFException());}delim.splitAsStream(line).forEach(tokens::addLast);}return tokens.pollFirst();} catch (IOException e) {throw new UncheckedIOException(e);}}public int nextInt() {return Integer.parseInt(nextString());}public double nextDouble() {return Double.parseDouble(nextString());}public long nextLong() {return Long.parseLong(nextString());}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();}}}