結果
問題 | No.1111 コード進行 |
ユーザー |
![]() |
提出日時 | 2020-07-10 21:32:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 880 bytes |
コンパイル時間 | 1,705 ms |
コンパイル使用メモリ | 169,676 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-11 07:59:48 |
合計ジャッジ時間 | 3,286 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } #define MOD 1000000007 int main() { int n = ri(); int m = ri(); int sum = ri(); struct Next { int from; int to; int cost; }; std::vector<Next> hens; for (int i = 0; i < m; i++) { int x = ri() - 1; int y = ri() - 1; hens.push_back({x, y, ri()}); } int dp[300][sum + 1]; memset(dp, 0, sizeof(dp)); for (int i = 0; i < 300; i++) dp[i][0] = 1; for (int i = 1; i < n; i++) { int next[300][sum + 1]; memset(next, 0, sizeof(next)); for (auto j : hens) { for (int k = 0; k <= sum - j.cost; k++) { next[j.to][k + j.cost] += dp[j.from][k]; if (next[j.to][k + j.cost] >= MOD) next[j.to][k + j.cost] -= MOD; } } memcpy(dp, next, sizeof(next)); } int64_t res = 0; for (int i = 0; i < 300; i++) res += dp[i][sum]; printf("%d\n", (int) (res % MOD)); return 0; }