結果

問題 No.30 たこやき工場
ユーザー ゴリポン先生
提出日時 2025-07-30 14:55:40
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 927 bytes
コンパイル時間 3,783 ms
コンパイル使用メモリ 199,320 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-07-30 14:55:46
合計ジャッジ時間 5,093 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

module main;
// https://kmjp.hatenablog.jp/entry/2015/07/13/0930 より
import std;

// 多次元配列をある値で埋める
void fill(A, T)(ref A a, T value) if (isArray!A)
{
	alias E = ElementType!A;
	static if (isArray!E) {
		foreach (ref e; a)
			fill(e, value);
	} else {
		a[] = value;
	}
}

int N, M;
alias P = Tuple!(int, int);
P[][] V;
long[][] memo;

void dfs(int cur)
{
	if (memo[cur][0] >= 0) return;
	fill(memo[cur], 0);
	if (V[cur].empty) {
		memo[cur][cur] = 1;
		return;
	}

	foreach (e; V[cur]) {
		dfs(e[0]);
		foreach (j; 0 .. N)
			memo[cur][j] += e[1] * memo[e[0]][j];
	}
}

void main()
{
	N = readln.chomp.to!int;
	M = readln.chomp.to!int;
	V = new P[][](N + 1);
	foreach (_; 0 .. M) {
		int p, q, r;
		readln.chomp.formattedRead("%d %d %d", p, q, r);
		V[r - 1] ~= P(p - 1, q);
	}
	memo = new long[][](N + 1, N + 1);
	fill(memo, -1);
	dfs(N - 1);
	foreach (i; 0 .. N - 1)
		writeln(memo[N - 1][i]);
}
0