結果
問題 | No.1749 ラムドスウイルスの感染拡大 |
ユーザー |
|
提出日時 | 2021-12-25 13:04:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 947 bytes |
コンパイル時間 | 1,559 ms |
コンパイル使用メモリ | 170,580 KB |
実行使用メモリ | 7,424 KB |
最終ジャッジ日時 | 2024-09-21 15:10:10 |
合計ジャッジ時間 | 2,800 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using Graph = vector<vector<int>>; using edge = pair<int,int>; using djikstra = priority_queue<edge, vector<edge>, greater<edge>>; const int INF = 1e+9; const ll LINF = (ll)pow(10,18); const int mod = INF + 7; const int lmod = 998244353; int gcd(int a, int b){ if(a%b == 0){ return b; } else { return gcd(b, a%b); } } int dp[1002][1002] = {0}; int main(){ int n,m,t; cin >> n >> m >> t; Graph g(n); int a,b; for(int i=0; i<m; i++){ cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } dp[0][0] = 1; for(int i=0; i<t; i++){ for(int j=0; j<n; j++){ if(dp[i][j] > 0){ for(auto v : g[j]){ dp[i+1][v] += dp[i][j]; dp[i+1][v] %= lmod; } } } } cout << dp[t][0] << endl; }