結果
問題 | No.19 ステージの選択 |
ユーザー |
|
提出日時 | 2020-08-27 16:59:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,002 bytes |
コンパイル時間 | 1,029 ms |
コンパイル使用メモリ | 78,220 KB |
最終ジャッジ日時 | 2025-01-13 15:22:33 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include <iostream> #include <vector> #include <queue> void solve() { int n; std::cin >> n; int sum = 0; std::vector<int> xs(n), vs(n), indeg(n, 0); for (int i = 0; i < n; ++i) { std::cin >> xs[i] >> vs[i]; sum += xs[i]; ++indeg[--vs[i]]; } std::queue<int> que; for (int v = 0; v < n; ++v) { if (indeg[v] == 0) que.push(v); } while (!que.empty()) { int v = que.front(); que.pop(); xs[v] = -1; int u = vs[v]; if (--indeg[u] == 0) que.push(u); } for (int s = 0; s < n; ++s) { if (xs[s] == -1) continue; int min = xs[s]; int v = s; while (vs[v] != s) { v = vs[v]; min = std::min(min, xs[v]); xs[v] = -1; } sum += min; } std::cout << sum / 2 << "." << sum % 2 * 5 << "\n"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }