結果
問題 |
No.1111 コード進行
|
ユーザー |
|
提出日時 | 2020-07-10 23:01:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 225 ms / 2,000 ms |
コード長 | 957 bytes |
コンパイル時間 | 371 ms |
コンパイル使用メモリ | 32,896 KB |
実行使用メモリ | 217,344 KB |
最終ジャッジ日時 | 2024-10-11 15:51:06 |
合計ジャッジ時間 | 2,936 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include<cstdio> struct Element{ int a,b; int c; }; long long f[305][305][305]; Element e[305]; const long long mod = 1e9+7; int main(){ int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i = 1; i <= m; i++){ int p,q,c; scanf("%d%d%d",&p,&q,&c); e[i].a = p, e[i].b = q, e[i].c = c; f[2][q][c] = (f[2][q][c]+1)%mod; } for(int i = 2; i <= n-1; i++){ for(int j = 0; j <= k; j++){ for(int t = 1; t <= m; t++){ int nextK = j+e[t].c; if(nextK<=k){ //printf("from %d %d %d to %d %d %d\n",i,e[t].a,j,i+1,e[t].b,nextK); f[i+1][e[t].b][nextK] += f[i][e[t].a][j]; if(f[i+1][e[t].b][nextK]>=mod) f[i+1][e[t].b][nextK] -= mod; } } } } long long ans = 0; for(int i = 1; i <= 300; i++) ans = (ans+f[n][i][k])%mod; printf("%lld\n",ans); return 0; }