Submission #1280985
Source Code Expand
import static java.lang.Math.*; import static java.util.Arrays.*; import java.util.*; import java.io.*; public class Main { void solve() { int N = sc.nextInt(); int M = sc.nextInt(); V[] vs = new V[N]; for (int i = 0; i < N; i++) vs[i] = new V(i); for (int i = 0; i < M; i++) { int a = sc.nextInt() - 1; int b = sc.nextInt() - 1; int c = sc.nextInt(); vs[a].add(vs[b], c); } long INF = 1L << 58; for (V v : vs) v.score = -INF; vs[0].score = 0; for (int step = 0; step < 3 * N + 10; step++) { for (V v : vs) { for (E e : v.es) { if (e.to.score < (v.score + e.w)) { e.to.score = v.score + e.w; if (step >= N) { e.to.score = INF; } } } } } long ans = vs[N-1].score; if (ans >= INF / 2) out.println("inf"); else out.println(ans); } class V { ArrayList<E> es = new ArrayList<E>(); int id; long score = 0; public V(int id) { this.id = id; } void add(V to, int w) { this.es.add(new E(to, w)); } } class E { V to; long w; E(V to, long w) { this.to = to; this.w = w; } } static void tr(Object... os) { System.err.println(deepToString(os)); } static void tr(int[][] as) { for (int[] a : as) tr(a); } void print(int[] a) { out.print(a[0]); for (int i = 1; i < a.length; i++) out.print(" " + a[i]); out.println(); } public static void main(String[] args) throws Exception { new Main().run(); } MyScanner sc = null; PrintWriter out = null; public void run() throws Exception { sc = new MyScanner(System.in); out = new PrintWriter(System.out); for (;sc.hasNext();) { solve(); out.flush(); } out.close(); } class MyScanner { String line; BufferedReader reader; StringTokenizer tokenizer; public MyScanner(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public void eat() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { line = reader.readLine(); if (line == null) { tokenizer = null; return; } tokenizer = new StringTokenizer(line); } catch (IOException e) { throw new RuntimeException(e); } } } public String next() { eat(); return tokenizer.nextToken(); } public String nextLine() { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } public boolean hasNext() { eat(); return (tokenizer != null && tokenizer.hasMoreElements()); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } } }
Submission Info
Submission Time | |
---|---|
Task | D - Score Attack |
User | hs484 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 3003 Byte |
Status | AC |
Exec Time | 257 ms |
Memory | 61248 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 400 / 400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 69 ms | 20308 KB |
sample_02.txt | AC | 70 ms | 19028 KB |
sample_03.txt | AC | 69 ms | 21332 KB |
subtask_1_1.txt | AC | 134 ms | 32884 KB |
subtask_1_10.txt | AC | 74 ms | 21460 KB |
subtask_1_11.txt | AC | 139 ms | 33172 KB |
subtask_1_12.txt | AC | 187 ms | 37452 KB |
subtask_1_13.txt | AC | 110 ms | 36692 KB |
subtask_1_14.txt | AC | 180 ms | 46928 KB |
subtask_1_15.txt | AC | 257 ms | 57856 KB |
subtask_1_16.txt | AC | 71 ms | 19284 KB |
subtask_1_17.txt | AC | 84 ms | 21588 KB |
subtask_1_18.txt | AC | 156 ms | 43348 KB |
subtask_1_19.txt | AC | 191 ms | 51056 KB |
subtask_1_2.txt | AC | 158 ms | 32244 KB |
subtask_1_20.txt | AC | 110 ms | 36948 KB |
subtask_1_21.txt | AC | 160 ms | 61248 KB |
subtask_1_22.txt | AC | 215 ms | 57556 KB |
subtask_1_23.txt | AC | 71 ms | 19540 KB |
subtask_1_24.txt | AC | 167 ms | 42880 KB |
subtask_1_25.txt | AC | 153 ms | 29048 KB |
subtask_1_26.txt | AC | 165 ms | 59476 KB |
subtask_1_27.txt | AC | 181 ms | 39504 KB |
subtask_1_3.txt | AC | 146 ms | 34420 KB |
subtask_1_4.txt | AC | 156 ms | 36976 KB |
subtask_1_5.txt | AC | 137 ms | 32988 KB |
subtask_1_6.txt | AC | 176 ms | 36408 KB |
subtask_1_7.txt | AC | 164 ms | 57332 KB |
subtask_1_8.txt | AC | 142 ms | 30036 KB |
subtask_1_9.txt | AC | 75 ms | 18516 KB |