結果
問題 | No.30 たこやき工場 |
ユーザー |
![]() |
提出日時 | 2017-11-01 22:51:01 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 271 ms / 5,000 ms |
コード長 | 1,536 bytes |
コンパイル時間 | 3,641 ms |
コンパイル使用メモリ | 79,828 KB |
実行使用メモリ | 58,944 KB |
最終ジャッジ日時 | 2024-12-21 05:26:56 |
合計ジャッジ時間 | 6,739 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.Map.Entry; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); final int N = sc.nextInt(); final int M = sc.nextInt(); int[] in_degs = new int[N]; ArrayList<HashMap<Integer, Long>> rev_adj = new ArrayList<HashMap<Integer, Long>>(); for(int i = 0; i < N; i++){ rev_adj.add(new HashMap<Integer, Long>()); } for(int i = 0; i < M; i++){ final int P = sc.nextInt() - 1; final long Q = sc.nextLong(); final int R = sc.nextInt() - 1; in_degs[R]++; if(!rev_adj.get(P).containsKey(R)){ rev_adj.get(P).put(R, Q); }else{ rev_adj.get(P).put(R, Math.min(Q, rev_adj.get(P).get(R))); } } LinkedList<Integer> queue = new LinkedList<Integer>(); long[][] comps = new long[N][N]; for(int i = 0; i < N; i++){ if(in_degs[i] != 0){ continue; } comps[i][i] = 1; queue.add(i); } while(!queue.isEmpty()){ final int node = queue.poll(); for(final Entry<Integer, Long> entry : rev_adj.get(node).entrySet()){ final int from = entry.getKey(); final long value = entry.getValue(); for(int i = 0; i < N; i++){ comps[from][i] += value * comps[node][i]; } in_degs[from]--; if(in_degs[from] == 0){ queue.add(from); } } } for(int i = 0; i < N - 1; i++){ System.out.println(comps[N - 1][i]); } } }