Submission #934933
Source Code Expand
import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; import java.util.function.BiFunction; public class Main { Scanner sc = new Scanner(System.in); public static void main(String[] args) { new Main().run(); } class Edge { int to; int cost; } int n, m, t; ArrayList<ArrayList<Edge>> list; ArrayList<ArrayList<Edge>> rev; long[] dijkstra(int atom) { long[] ret = new long[n + 1]; Arrays.fill(ret, 1L << 56); PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> Long.compare(ret[a], ret[b])); ret[atom] = 0; queue.add(atom); boolean[] done = new boolean[n + 1]; while (queue.size() > 0) { int id = queue.poll(); if (done[id]) { continue; } done[id] = true; for (Edge next : list.get(id)) { if (ret[next.to] > ret[id] + next.cost) { ret[next.to] = ret[id] + next.cost; queue.add(next.to); } } } return ret; } long[] to1; long[] dijkstra2(int atom) { long[] ret = new long[n + 1]; Arrays.fill(ret, 1L << 60); PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> Long.compare(ret[a], ret[b])); ret[atom] = 0; queue.add(atom); boolean[] done = new boolean[n + 1]; while (queue.size() > 0) { int id = queue.poll(); if (done[id]) { continue; } done[id] = true; for (Edge next : rev.get(id)) { if (ret[next.to] > ret[id] + next.cost) { ret[next.to] = ret[id] + next.cost; queue.add(next.to); } } } return ret; } void run() { n = ni(); m = ni(); t = ni(); int[] A = new int[n + 1]; for (int i = 1; i <= n; ++i) { A[i] = ni(); } list = new ArrayList<>(); for (int i = 0; i <= n; ++i) { list.add(new ArrayList<>()); } rev = new ArrayList<>(); for (int i = 0; i <= n; ++i) { rev.add(new ArrayList<>()); } for (int i = 0; i < m; ++i) { int a = ni(); int b = ni(); int c = ni(); Edge e = new Edge(); e.to = b; e.cost = c; list.get(a).add(e); Edge r = new Edge(); r.to = a; r.cost = c; rev.get(b).add(r); } long[] from1 = dijkstra(1); long[] to1 = dijkstra2(1); long max = 0; for (int i = 1; i <= n; ++i) { long now = Math.min(t, from1[i] + to1[i]); max = Math.max(max, (t - now) * A[i]); } System.out.println(max); } int ni() { return Integer.parseInt(sc.next()); } void debug(Object... os) { System.err.println(Arrays.deepToString(os)); } class BIT<T> { int n; ArrayList<T> bit; BiFunction<T, T, T> bif; BIT(int n, BiFunction<T, T, T> bif, T defaultValue) { this.n = n; bit = new ArrayList<>(n + 1); for (int i = 0; i < n + 1; ++i) { bit.add(defaultValue); } this.bif = bif; } void update(int i, T v) { for (int x = i; x <= n; x += x & -x) { bit.set(x, bif.apply(bit.get(x), v)); } } T reduce(int i, T defaultValue) { T ret = defaultValue; for (int x = i; x > 0; x -= x & -x) { ret = bif.apply(ret, bit.get(x)); } return ret; } } }
Submission Info
Submission Time | |
---|---|
Task | D - トレジャーハント |
User | arukuka |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 3451 Byte |
Status | AC |
Exec Time | 1016 ms |
Memory | 71764 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 50 / 50 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 10_rand_01.txt, 10_rand_02.txt, 10_rand_03.txt, 10_rand_04.txt, 10_rand_05.txt, 10_rand_06.txt, 10_rand_07.txt, 10_rand_08.txt, 10_rand_09.txt, 10_rand_10.txt, 10_rand_12.txt, 10_rand_13.txt, 30_max_01.txt, 30_max_02.txt, 30_max_03.txt, 30_max_04.txt, 30_max_05.txt, 30_max_06.txt, 40_corner_01.txt, 40_corner_02.txt, 40_corner_03.txt, 40_corner_04.txt, 50_small_01.txt, 50_small_02.txt, 50_small_03.txt, 50_small_04.txt, 50_small_05.txt, 50_small_06.txt, 50_small_07.txt, 50_small_08.txt, 50_small_09.txt, 50_small_10.txt, 60_hand_01.txt, 60_hand_02.txt, 60_hand_03.txt, 60_hand_04.txt, 70_max_01.txt, 70_max_02.txt, 70_max_03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | AC | 221 ms | 14544 KB |
00_example_02.txt | AC | 217 ms | 14536 KB |
00_example_03.txt | AC | 225 ms | 14916 KB |
10_rand_01.txt | AC | 398 ms | 27076 KB |
10_rand_02.txt | AC | 580 ms | 37624 KB |
10_rand_03.txt | AC | 444 ms | 31040 KB |
10_rand_04.txt | AC | 322 ms | 21648 KB |
10_rand_05.txt | AC | 462 ms | 32932 KB |
10_rand_06.txt | AC | 454 ms | 33048 KB |
10_rand_07.txt | AC | 433 ms | 32168 KB |
10_rand_08.txt | AC | 389 ms | 27372 KB |
10_rand_09.txt | AC | 468 ms | 30808 KB |
10_rand_10.txt | AC | 317 ms | 20876 KB |
10_rand_12.txt | AC | 631 ms | 40708 KB |
10_rand_13.txt | AC | 662 ms | 42004 KB |
30_max_01.txt | AC | 891 ms | 61436 KB |
30_max_02.txt | AC | 944 ms | 61736 KB |
30_max_03.txt | AC | 786 ms | 59488 KB |
30_max_04.txt | AC | 778 ms | 68852 KB |
30_max_05.txt | AC | 834 ms | 68504 KB |
30_max_06.txt | AC | 792 ms | 67896 KB |
40_corner_01.txt | AC | 898 ms | 71052 KB |
40_corner_02.txt | AC | 900 ms | 71764 KB |
40_corner_03.txt | AC | 1016 ms | 71016 KB |
40_corner_04.txt | AC | 953 ms | 71556 KB |
50_small_01.txt | AC | 303 ms | 18048 KB |
50_small_02.txt | AC | 226 ms | 14672 KB |
50_small_03.txt | AC | 251 ms | 15696 KB |
50_small_04.txt | AC | 252 ms | 17864 KB |
50_small_05.txt | AC | 324 ms | 19000 KB |
50_small_06.txt | AC | 314 ms | 18944 KB |
50_small_07.txt | AC | 234 ms | 14792 KB |
50_small_08.txt | AC | 218 ms | 14532 KB |
50_small_09.txt | AC | 282 ms | 16172 KB |
50_small_10.txt | AC | 269 ms | 15620 KB |
60_hand_01.txt | AC | 218 ms | 14920 KB |
60_hand_02.txt | AC | 219 ms | 14788 KB |
60_hand_03.txt | AC | 222 ms | 14528 KB |
60_hand_04.txt | AC | 217 ms | 15052 KB |
70_max_01.txt | AC | 530 ms | 33128 KB |
70_max_02.txt | AC | 560 ms | 34044 KB |
70_max_03.txt | AC | 562 ms | 33048 KB |