結果
問題 | No.30 たこやき工場 |
ユーザー |
|
提出日時 | 2020-03-30 15:38:28 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 261 ms / 5,000 ms |
コード長 | 1,271 bytes |
コンパイル時間 | 3,436 ms |
コンパイル使用メモリ | 78,980 KB |
実行使用メモリ | 57,324 KB |
最終ジャッジ日時 | 2024-12-21 05:30:28 |
合計ジャッジ時間 | 7,767 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; class Edge{ int src,dst,need; public Edge(int src,int dst,int cost) { this.src=src; this.dst=dst; this.need=cost; } } class Main { public static void main(String[] args) { new Main().run(); } void dfs(int cur,int par,ArrayList<Edge>[] g,long[] dp) { if(dp[cur]>0)return; for(Edge e:g[cur]) { if(e.dst==par)continue; dfs(e.dst,cur,g,dp); dp[cur]+=(long)dp[e.dst]*e.need; } } void run() { Scanner sc=new Scanner(System.in); int N=sc.nextInt(); int M=sc.nextInt(); ArrayList<Edge>[] g=new ArrayList[N]; for(int i=0;i<g.length;++i)g[i]=new ArrayList<>(); long[] dp=new long[N]; int[] indeg=new int[N]; int[] outdeg=new int[N]; dp[N-1]=1; for(int i=0;i<M;++i) { int src=sc.nextInt(); int need=sc.nextInt(); int dst=sc.nextInt(); --src;--dst; g[src].add(new Edge(src,dst,need)); outdeg[src]++; indeg[dst]++; } for(int i=0;i<N;++i) { dfs(i,-1,g,dp); } for(int i=0;i<N-1;++i) { if(indeg[i]==0) { System.out.println(dp[i]); }else { System.out.println(0); } } } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }