結果
問題 | No.30 たこやき工場 |
ユーザー |
![]() |
提出日時 | 2018-10-31 08:37:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 17 ms / 5,000 ms |
コード長 | 1,365 bytes |
コンパイル時間 | 2,344 ms |
コンパイル使用メモリ | 203,836 KB |
最終ジャッジ日時 | 2025-01-06 15:11:39 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; using i64 = int64_t; using vi = vector<i64>; using vvi = vector<vi>; using ii = pair<int, i64>; int main() { int n, m; cin >> n >> m; vector<set<ii>> ins(n), outs(n); for (int i = 0; i < m; i++) { int a, w, b; cin >> a >> w >> b; a--; b--; ins[b].insert(ii(a, w)); outs[a].insert(ii(b, w)); } vi needs(n), visited(n); needs.back() = 1; while (1) { int change = 0; for (int i = 0; i < n; i++) { if (visited[i]) continue; if (outs[i].empty()) { // cout << "Found empty: " << i << endl; visited[i] = 1; // if (needs[i] == 0) continue; for (auto& e: ins[i]) { int k = e.first; // cout << "node " << k << " is going to " << i << " with cost " << e.second << endl; needs[k] += needs[i] * e.second; // cout << "need[k] has updated: " << needs[k] << endl; outs[k].erase(ii(i, e.second)); } change = 1; } } if (!change) break; } for (int i = 0; i < n - 1; i++) { // cout << needs[i] << endl; cout << (ins[i].empty() ? needs[i] : 0) << endl; } }