結果
問題 |
No.1111 コード進行
|
ユーザー |
|
提出日時 | 2020-07-10 22:11:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 230 ms / 2,000 ms |
コード長 | 1,338 bytes |
コンパイル時間 | 1,825 ms |
コンパイル使用メモリ | 193,268 KB |
最終ジャッジ日時 | 2025-01-11 18:37:03 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
/*** author: yuji9511 ***/ #include <bits/stdc++.h> using namespace std; using ll = long long; using lpair = pair<ll, ll>; const ll MOD = 1e9+7; const ll INF = 1e18; #define rep(i,m,n) for(ll i=(m);i<(n);i++) #define rrep(i,m,n) for(ll i=(m);i>=(n);i--) #define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];}; void print() {} template <class H,class... T> void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);} ll dp[310][310][310] = {}; void solve(){ ll N,M,K; cin >> N >> M >> K; ll P[310], Q[310], C[310]; ll dist[310][310] = {}; rep(i,0,300){ rep(j,0,300){ if(i == j) dist[i][j] = 0; else dist[i][j] = INF; } } rep(i,0,M){ cin >> P[i] >> Q[i] >> C[i]; P[i]--; Q[i]--; dist[P[i]][Q[i]] = C[i]; } rep(i,0,300){ dp[0][i][0] = 1; } rep(n,0,N-1){ rep(i,0,M){ rep(k,0,K+1){ if(k - C[i] >= 0){ dp[n+1][Q[i]][k] += dp[n][P[i]][k - C[i]]; dp[n+1][Q[i]][k] %= MOD; } } } } ll ans = 0; rep(i,0,300){ ans += dp[N-1][i][K]; ans %= MOD; } print(ans); } int main(){ cin.tie(0); ios::sync_with_stdio(false); solve(); }