Submission #1609504
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; boolean updflg = true; int cnt = 0; while (updflg) { updflg = false; 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; updflg = true; flg[e.b] = true; } } } cnt++; if (cnt > n) return false; } return true; } 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 | 0 |
Code Size | 1910 Byte |
Status | WA |
Exec Time | 296 ms |
Memory | 46880 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 92 ms | 20820 KB |
sample_02.txt | AC | 92 ms | 20688 KB |
sample_03.txt | AC | 94 ms | 19284 KB |
subtask_1_1.txt | AC | 152 ms | 28352 KB |
subtask_1_10.txt | AC | 111 ms | 22228 KB |
subtask_1_11.txt | AC | 172 ms | 25840 KB |
subtask_1_12.txt | AC | 243 ms | 39244 KB |
subtask_1_13.txt | AC | 114 ms | 18644 KB |
subtask_1_14.txt | AC | 243 ms | 41852 KB |
subtask_1_15.txt | AC | 296 ms | 46880 KB |
subtask_1_16.txt | AC | 97 ms | 18640 KB |
subtask_1_17.txt | AC | 108 ms | 21716 KB |
subtask_1_18.txt | AC | 163 ms | 25628 KB |
subtask_1_19.txt | AC | 171 ms | 27560 KB |
subtask_1_2.txt | AC | 157 ms | 26604 KB |
subtask_1_20.txt | AC | 116 ms | 21204 KB |
subtask_1_21.txt | AC | 170 ms | 25080 KB |
subtask_1_22.txt | AC | 174 ms | 26748 KB |
subtask_1_23.txt | WA | 99 ms | 18768 KB |
subtask_1_24.txt | AC | 186 ms | 27484 KB |
subtask_1_25.txt | WA | 190 ms | 30152 KB |
subtask_1_26.txt | AC | 217 ms | 39680 KB |
subtask_1_27.txt | WA | 221 ms | 44260 KB |
subtask_1_3.txt | AC | 152 ms | 26288 KB |
subtask_1_4.txt | AC | 164 ms | 26184 KB |
subtask_1_5.txt | AC | 201 ms | 35584 KB |
subtask_1_6.txt | AC | 226 ms | 45676 KB |
subtask_1_7.txt | AC | 151 ms | 25684 KB |
subtask_1_8.txt | AC | 152 ms | 26352 KB |
subtask_1_9.txt | AC | 92 ms | 19924 KB |