結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
|
提出日時 | 2019-05-10 22:13:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 1,415 bytes |
コンパイル時間 | 1,756 ms |
コンパイル使用メモリ | 176,596 KB |
実行使用メモリ | 5,504 KB |
最終ジャッジ日時 | 2024-07-02 01:03:10 |
合計ジャッジ時間 | 3,270 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct UnionFind{vector<int> data;UnionFind(int size) : data(size, -1){}void unite(int x, int y){x = root(x);y = root(y);if (x != y){if (data[y] < data[x]) swap(x, y);data[x] += data[y];data[y] = x;}}int root(int x) {return data[x] < 0 ? x : data[x] = root(data[x]);}int size(int x) {return -data[root(x)];}};int main(){cin.tie(0);ios::sync_with_stdio(false);int N, M, K;cin >> N >> M >> K;vector<pair<int, int>> edges(M, pair<int, int>());vector<pair<int, int>> cs(M, pair<int, int>());vector<int> es(K, 0);long long total_cost = 0;for (int i = 0; i < M; ++i){int a, b, c;cin >> a >> b >> c;edges[i] = make_pair(a-1, b-1);cs[i] = make_pair(c, i);total_cost += c;}for (auto &e: es) cin >> e;UnionFind uf(N);long long cost = 0;for (auto e: es){cost += cs[e - 1].first;uf.unite(edges[e-1].first, edges[e-1].second);}sort(cs.begin(), cs.end());for (auto &ci: cs){int i = ci.second;int a = edges[i].first;int b = edges[i].second;if (uf.root(a) == uf.root(b)) continue;cost += ci.first;uf.unite(a, b);}cout << total_cost - cost << endl;return 0;}