結果
問題 | No.807 umg tours |
ユーザー | neko_the_shadow |
提出日時 | 2019-05-17 12:55:01 |
言語 | Java (openjdk 23) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,246 bytes |
コンパイル時間 | 4,916 ms |
コンパイル使用メモリ | 92,460 KB |
実行使用メモリ | 248,060 KB |
最終ジャッジ日時 | 2024-11-23 19:31:54 |
合計ジャッジ時間 | 36,670 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 TLE * 1 |
ソースコード
package _0807;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.io.PrintWriter;import java.util.Arrays;import java.util.HashMap;import java.util.Map;import java.util.Map.Entry;import java.util.PriorityQueue;import java.util.stream.IntStream;public class Main {public static void main(String[] args) throws IOException {BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));String[] first = stdin.readLine().split(" ");int n = Integer.parseInt(first[0]);int m = Integer.parseInt(first[1]);Map<Integer, Map<Integer, Long>> costs = new HashMap<>();for (int i = 0; i < m; i++) {String[] line = stdin.readLine().split(" ");int a = Integer.parseInt(line[0]) - 1;int b = Integer.parseInt(line[1]) - 1;long c = Long.parseLong(line[2]);costs.computeIfAbsent(a, unused -> new HashMap<>()).put(b, c);costs.computeIfAbsent(b, unused -> new HashMap<>()).put(a, c);}long[] d1 = new long[n];long[] d2 = new long[n];PriorityQueue<Tuple> q = new PriorityQueue<>();Arrays.fill(d1, Long.MAX_VALUE);Arrays.fill(d2, Long.MAX_VALUE);d1[0] = 0;d2[0] = 0;q.add(new Tuple(0, 0, false));q.add(new Tuple(0, 0, true));while (!q.isEmpty()) {Tuple t = q.poll();int u = t.ptr;if (!costs.containsKey(u)) {continue;}if (t.skipped) {for (Entry<Integer, Long> e : costs.get(u).entrySet()) {int v = e.getKey();long d = e.getValue();if (d2[u] + d < d2[v]) {d2[v] = d2[u] + d;q.add(new Tuple(d2[v], v, true));}}} else {for (Entry<Integer, Long> e : costs.get(u).entrySet()) {int v = e.getKey();long d = e.getValue();if (d1[u] + d < d1[v]) {d1[v] = d1[u] + d;q.add(new Tuple(d1[v], v, false));}if (d1[u] < d2[v]) {d2[v] = d1[u];q.add(new Tuple(d2[v], v, true));}}}}PrintWriter stdout = new PrintWriter(System.out);IntStream.range(0, n).mapToLong(i -> d1[i] + d2[i]).forEach(stdout::println);stdout.flush();}private static class Tuple implements Comparable<Tuple>{private long d;private int ptr;private boolean skipped;public Tuple(long d, int ptr, boolean skipped) {super();this.d = d;this.ptr = ptr;this.skipped = skipped;}@Overridepublic int compareTo(Tuple other) {return Long.compare(this.d, other.d);}}}