結果
問題 | No.30 たこやき工場 |
ユーザー |
|
提出日時 | 2020-08-22 05:33:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,149 bytes |
コンパイル時間 | 1,025 ms |
コンパイル使用メモリ | 86,420 KB |
最終ジャッジ日時 | 2025-01-13 06:45:59 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream> #include <vector> #include <queue> template <class T> std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); } using lint = long long; void solve() { int n, m; std::cin >> n >> m; std::vector<std::vector<std::pair<int, int>>> graph(n); std::vector<int> indeg(n, 0); while (m--) { int u, q, v; std::cin >> u >> q >> v; --u, --v; graph[u].emplace_back(q, v); ++indeg[v]; } std::queue<int> que; auto ans = vec(n, vec(n, 0LL)); for (int v = 0; v < n; ++v) { if (indeg[v] == 0) { que.push(v); ans[v][v] = 1; } } while (!que.empty()) { int u = que.front(); que.pop(); for (auto [q, v] : graph[u]) { for (int i = 0; i < n; ++i) { ans[v][i] += ans[u][i] * q; } if (--indeg[v] == 0) que.push(v); } } for (int i = 0; i < n - 1; ++i) { std::cout << ans[n - 1][i] << "\n"; } } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }