Submission #1609541
Source Code Expand
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { int n, m; ArrayList<ArrayList<Edge>> es; long[] dist; private final long INF = Long.MAX_VALUE; public static void main(String[] args) { Main m = new Main(); m.read(); m.solve(); } private void read() { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); es = new ArrayList<>(n); for (int i = 0; i < n; i++) es.add(new ArrayList<>()); for (int i = 0; i < m; i++) { int a = sc.nextInt() - 1; int b = sc.nextInt() - 1; long c = sc.nextLong(); es.get(a).add(new Edge(a, b, -c)); } } private void solve() { boolean b = bellman(); if (!b) System.out.println(-dist[n-1]); else System.out.println("inf"); } private boolean bellman() { dist = new long[n]; Arrays.fill(dist, INF); dist[0] = 0; boolean[] flg = new boolean[n]; flg[0] = true; for (int i = 0; i < n+1; i++) { for (ArrayList<Edge> ls: es) { for (Edge e: ls) { if (flg[e.a] && dist[e.b] > dist[e.a] + e.c) { dist[e.b] = dist[e.a] + e.c; flg[e.b] = true; } } } } boolean[] nflg = new boolean[n]; for (int i = 0; i < n; i++) { for (ArrayList<Edge> ls: es) { for (Edge e: ls) { if (flg[e.a] && dist[e.b] > dist[e.a] + e.c) { dist[e.b] = dist[e.a] + e.c; nflg[e.b] = true; } if (nflg[e.a]) nflg[e.b] = true; } } } return nflg[n-1]; } private class Edge { int a, b; long c; Edge (int a, int b, long c) { this.a = a; this.b = b; this.c = c; } } }
Submission Info
Submission Time | |
---|---|
Task | D - Score Attack |
User | nmjiri |
Language | Java8 (OpenJDK 1.8.0) |
Score | 400 |
Code Size | 2223 Byte |
Status | AC |
Exec Time | 365 ms |
Memory | 48052 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 | 91 ms | 21844 KB |
sample_02.txt | AC | 93 ms | 19412 KB |
sample_03.txt | AC | 95 ms | 21716 KB |
subtask_1_1.txt | AC | 197 ms | 34428 KB |
subtask_1_10.txt | AC | 111 ms | 19924 KB |
subtask_1_11.txt | AC | 198 ms | 30108 KB |
subtask_1_12.txt | AC | 275 ms | 41628 KB |
subtask_1_13.txt | AC | 163 ms | 44388 KB |
subtask_1_14.txt | AC | 277 ms | 47024 KB |
subtask_1_15.txt | AC | 365 ms | 45760 KB |
subtask_1_16.txt | AC | 108 ms | 19668 KB |
subtask_1_17.txt | AC | 115 ms | 18900 KB |
subtask_1_18.txt | AC | 279 ms | 38892 KB |
subtask_1_19.txt | AC | 317 ms | 46736 KB |
subtask_1_2.txt | AC | 290 ms | 44772 KB |
subtask_1_20.txt | AC | 164 ms | 44132 KB |
subtask_1_21.txt | AC | 269 ms | 40736 KB |
subtask_1_22.txt | AC | 352 ms | 42820 KB |
subtask_1_23.txt | AC | 107 ms | 21332 KB |
subtask_1_24.txt | AC | 286 ms | 38472 KB |
subtask_1_25.txt | AC | 213 ms | 34376 KB |
subtask_1_26.txt | AC | 316 ms | 48052 KB |
subtask_1_27.txt | AC | 278 ms | 43996 KB |
subtask_1_3.txt | AC | 262 ms | 40608 KB |
subtask_1_4.txt | AC | 292 ms | 44280 KB |
subtask_1_5.txt | AC | 227 ms | 42564 KB |
subtask_1_6.txt | AC | 270 ms | 37676 KB |
subtask_1_7.txt | AC | 293 ms | 43936 KB |
subtask_1_8.txt | AC | 268 ms | 44924 KB |
subtask_1_9.txt | AC | 94 ms | 21716 KB |