結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2018-10-19 22:50:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 2,432 bytes |
コンパイル時間 | 1,164 ms |
コンパイル使用メモリ | 107,492 KB |
実行使用メモリ | 11,988 KB |
最終ジャッジ日時 | 2024-11-18 22:02:03 |
合計ジャッジ時間 | 2,763 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<iostream>#include<vector>#include<queue>#include<stack>#include<string>#include<cmath>#include<algorithm>#include<bitset>#include<map>#include<unordered_map>#include<functional>#include<set>#include<numeric>#pragma regionusing namespace std;#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)#define rep(i,n) FOR(i,0LL,n)#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)#define rrep(i,n) RFOR(i,0LL,n)#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())#define SUM(a) accumulate(all(a),0LL)#define pb push_back#define endl '\n'typedef long long int ll;typedef vector<ll> vll;typedef vector<vll> vvll;typedef pair<ll, ll> pll;typedef vector<pll> vpll;typedef vector<string> vs;typedef map<ll, ll> MAP;const ll inf = 2222222222222222222LL;const ll mod = 1000000007LL;ll n = 0, m = 0, ans = 0, cnt = 0, tmp = 0, ma = -inf, mi = inf;string s;bool ok = true, flag = false;ll dx[5] = { 1,-1,0,0,0 }, dy[5] = { 0,0,1,-1,0 };ll ddx[9] = { 1,-1,0,0,1,1,-1,-1,0 }, ddy[9] = { 0,0,1,-1,1,-1,1,-1,0 };#pragma endregion#define MAX 222222struct UnionFind {vll rank, par, data;void set(ll n) {rank.resize(n + 1, 0);par.resize(n + 1, 0);data.resize(n + 1, 1);rep(i, n + 1) par[i] = i;}ll root(ll x) {if (x != par[x]) par[x] = root(par[x]);return par[x];}ll size(ll x) {return data[root(x)];}void unite(ll a, ll b) {ll x = root(a);ll y = root(b);if (x == y) return;if (rank[x] > rank[y]) {par[y] = x;data[x] += data[y];}else {par[x] = y;data[y] += data[x];if (rank[x] == rank[y]) rank[y]++;}}bool same(ll a, ll b) {return root(a) == root(b);}};ll a[MAX], b[MAX], c[MAX], d[MAX];int main(void) {ios::sync_with_stdio(false);cin.tie(0);ll k;vector<pair<ll, pll>> v;UnionFind u;cin >> n >> m >> k;u.set(n);rep(i, m) {cin >> a[i] >> b[i] >> c[i];}rep(i, k) {cin >> tmp;tmp--;d[tmp]++;u.unite(a[tmp], b[tmp]);}rep(i, m) {if (d[i]) continue;v.pb(make_pair(c[i], pll(a[i], b[i])));}sort(all(v));rep(i, v.size()) {if (u.same(v[i].second.first, v[i].second.second)) {ans += v[i].first;}else {u.unite(v[i].second.first, v[i].second.second);}}cout << ans << endl;return 0;}