結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
|
提出日時 | 2018-10-19 22:01:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 1,875 bytes |
コンパイル時間 | 814 ms |
コンパイル使用メモリ | 92,112 KB |
実行使用メモリ | 6,400 KB |
最終ジャッジ日時 | 2024-11-24 09:07:50 |
合計ジャッジ時間 | 3,475 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <limits>#include <iostream>#include <algorithm>#include <vector>#include <iomanip>#include <map>#include <queue>static const int MOD = 1000000007;using ll = long long;using u32 = unsigned;using namespace std;template<class T>constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;template <typename T>struct edge {int from, to;T cost;edge(int to, T cost) : from(-1), to(to), cost(cost) {}edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}explicit operator int() const {return to;}};class UnionFind {vector<int> uni;int n;public:explicit UnionFind(int n) : uni(static_cast<u32>(n), -1) , n(n){};int root(int a){if (uni[a] < 0) return a;else return (uni[a] = root(uni[a]));}bool unite(int a, int b) {a = root(a);b = root(b);if(a == b) return false;if(uni[a] > uni[b]) swap(a, b);uni[a] += uni[b];uni[b] = a;return true;}};template< typename T >T kruskal(vector<edge<T>> &G, int V){sort(begin(G), end(G), [](const edge< T > &a, const edge< T > &b) { return (a.cost < b.cost); });UnionFind tree(V);T ret = 0;for(auto &e : G) {if(tree.unite(e.from, e.to)) ret += e.cost;}return (ret);}int main() {int n, m, k;cin >> n >> m >> k;vector<int> va(m), vb(m), vc(m);for (int i = 0; i < m; ++i) {scanf("%d%d%d", &va[i], &vb[i], &vc[i]);}for (int i = 0; i < k; ++i) {int e;scanf("%d", &e);vc[e-1] = 0;}ll sum = 0;for (int i = 0; i < m; ++i) {sum += vc[i];}vector<edge<ll>> v;v.reserve(m);for (int i = 0; i < m; ++i) {v.emplace_back(va[i]-1, vb[i]-1, (ll)vc[i]);}cout << sum - kruskal(v, n) << "\n";return 0;}