結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2018-10-19 22:15:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,783 bytes |
コンパイル時間 | 1,806 ms |
コンパイル使用メモリ | 175,884 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-18 21:02:08 |
合計ジャッジ時間 | 3,337 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define repeat(i, x) for (int64_t i = 0; (i) < (int64_t)(x); (i)++)// tubo28 is godstruct uf_tree {std::vector<int> parent;int __size;uf_tree(int size_) : parent(size_, -1), __size(size_) {}void unite(int x, int y) {if ((x = find(x)) != (y = find(y))) {if (parent[y] < parent[x]) std::swap(x, y);parent[x] += parent[y];parent[y] = x;__size--;}}bool is_same(int x, int y) { return find(x) == find(y); }int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); }int size(int x) { return -parent[find(x)]; }int size() { return __size; }};namespace TaskE {struct Edge {int u, v;int64_t cost;bool operator<(const Edge& e) const {return cost < e.cost;}};int n_, m_, k_;void solve() {cin >> n_ >> m_ >> k_;int64_t sum = 0;vector<Edge> edges(m_);repeat (i, m_) {cin >> edges[i].u >> edges[i].v >> edges[i].cost;edges[i].u--;edges[i].v--;sum += edges[i].cost;}uf_tree uf(n_);int64_t cost = 0;repeat (i, k_) {int e;cin >> e; e--;uf.unite(edges[e].u, edges[e].v);cost += edges[e].cost;}sort(edges.begin(), edges.end());for (auto& e : edges) {if (!uf.is_same(e.u, e.v)) {uf.unite(e.u, e.v);cost += e.cost;}}cout << sum - cost << endl;}}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);TaskE::solve();return 0;}