結果
問題 | No.30 たこやき工場 |
ユーザー |
![]() |
提出日時 | 2015-04-15 21:22:42 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 837 bytes |
コンパイル時間 | 1,494 ms |
コンパイル使用メモリ | 171,352 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-21 05:19:25 |
合計ジャッジ時間 | 2,274 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define MAX 99999999 int N, M; vector<int> P(1500), Q(1500), R(1500); vector<int> cost(100); vector<vector<pair<int, int>>> e(100); vector<vector<long long>> dp(150); vector<long long >dfs(int a){ if (dp[a].size() != 0) return dp[a]; vector<long long> ret(N); if (cost[a] != 1){ for (auto i : e[a]){ vector<long long> add = dfs(i.second); for (int j = 0; j < N; j++) { ret[j] += add[j] * i.first; } } } else ret[a] = 1; return dp[a] = ret; } int main() { cin >> N >> M; for (int i = 0; i < N; i++) { cost[i] = 1; } for (int i = 0; i < M; i++) { cin >> P[i] >> Q[i] >> R[i]; P[i]--; R[i]--; cost[R[i]] = MAX; e[R[i]].push_back(make_pair(Q[i], P[i])); } auto ans = dfs(N - 1); for (int i = 0; i < N - 1; i++) { cout << ans[i] << endl; } }