結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
|
提出日時 | 2018-10-19 21:58:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 116 ms / 2,000 ms |
コード長 | 1,210 bytes |
コンパイル時間 | 1,951 ms |
コンパイル使用メモリ | 210,184 KB |
最終ジャッジ日時 | 2025-01-06 14:38:39 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; signed main() { ios::sync_with_stdio(false); int N, M, K; cin >> N >> M >> K; vector<tuple<int, int, int>> E(M); for (int i = 0; i < M; ++i) { int u, v, w; cin >> u >> v >> w; E[i] = make_tuple(w, u - 1, v - 1); } set<int> taken; for (int i = 0; i < K; ++i) { int e; cin >> e; taken.emplace(e - 1); } vector<int> fa(N); iota(fa.begin(), fa.end(), 0); function<int(int)> find = [&](int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }; auto unite = [&](int x, int y) { int a = find(x); int b = find(y); if (a == b) return false; fa[a] = b; return true; }; int64_t ans = 0; for (int i = 0; i < M; ++i) ans += get<0>(E[i]); for (int i : taken) { int w, u, v; tie(w, u, v) = E[i]; unite(u, v); ans -= w; } vector<int> eord(M); iota(eord.begin(), eord.end(), 0); sort(eord.begin(), eord.end(), [&](int i, int j) { return get<0>(E[i]) < get<0>(E[j]); }); for (int i = 0; i < M; ++i) { if (taken.count(eord[i])) continue; int w, u, v; tie(w, u, v) = E[eord[i]]; if (unite(u, v)) ans -= w; } cout << ans << endl; return 0; }