結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2019-04-24 18:43:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 3,403 bytes |
コンパイル時間 | 1,866 ms |
コンパイル使用メモリ | 179,236 KB |
実行使用メモリ | 7,400 KB |
最終ジャッジ日時 | 2024-11-08 14:44:43 |
合計ジャッジ時間 | 4,167 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#define _USE_MATH_DEFINES#define _CRT_SECURE_NO_WARNINGS#include <bits/stdc++.h>using namespace std;/*BigInteger#include <boost/multiprecision/cpp_dec_float.hpp>#include <boost/multiprecision/cpp_int.hpp>#include <boost/rational.hpp>namespace xxx = boost::multiprecision;using Bint = xxx::cpp_int;using Real = xxx::number<xxx::cpp_dec_float<1024>>;*/#define int long long#define pb(x) push_back(x)#define m0(x) memset((x), 0, sizeof(x))#define mm(x) memset((x), -1, sizeof(x))//container#define ALL(x) (x).begin(), (x).end()#define RALL(a) (a).rbegin(), (a).rend()#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)#define EXIST(s, e) ((s).find(e) != (s).end())#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());#define PERM(c) \sort(ALL(c)); \for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))// debug#define GET_VAR_NAME(variable) #variable#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;// bit_macro#define bit(n) (1LL << (n))#define bitset(a, b) (a) |= (1 << (b))#define bitunset(a, b) (a) &= ~(1 << (b))#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)#define bitcount(a) __builtin_popcountll((a))//typedeftypedef long long lint;typedef unsigned long long ull;typedef complex<long double> Complex;typedef pair<int, int> P;typedef tuple<int, int, int> TP;typedef vector<int> vec;typedef vector<vec> mat;//constantconstexpr int INF = (int)1e18;constexpr int MOD = (int)1e9 + 7;constexpr double PI = (double)acos(-1);constexpr double EPS = (double)1e-10;constexpr int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};constexpr int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};//template <typename T>void chmax(T &a, T b) { a = max(a, b); }template <typename T>void chmin(T &a, T b) { a = min(a, b); }//inline int toInt(string s) {int v;istringstream sin(s);sin >> v;return v;}template <class T>inline string toString(T x) {ostringstream sout;sout << x;return sout.str();}//struct Accelerate_Cin {Accelerate_Cin() {cin.tie(0);ios::sync_with_stdio(0);cout << fixed << setprecision(20);};};struct edge {int to, from, cost;};struct UnionFind {vector<int> data;UnionFind(int sz) {data.assign(sz, -1);}bool same(int x, int y) {return find(x) == find(y);}bool unite(int x, int y) {x = find(x), y = find(y);if (x == y) return (false);if (data[x] > data[y]) swap(x, y);data[x] += data[y];data[y] = x;return (true);}int find(int k) {if (data[k] < 0) return (k);return (data[k] = find(data[k]));}int size(int k) {return (-data[find(k)]);}};int N, M, K, sum = 0;vector<edge> G;map<P, int> ng;UnionFind uf(101010);signed main() {cin >> N >> M >> K;for (int i = 0; i < M; i++) {int a, b, c;cin >> a >> b >> c;a--, b--;G.push_back({a, b, c});sum += c;}int ans = 0;for (int i = 0; i < K; i++) {int tmp;cin >> tmp;tmp--;int a = G[tmp].to, b = G[tmp].from;uf.unite(a, b);ans += G[tmp].cost;}sort(ALL(G), [&](const edge &e1, const edge &e2) {return e1.cost < e2.cost;});for (auto x : G) {int a = x.to, b = x.from, c = x.cost;if (!uf.same(a, b)) {ans += c;uf.unite(a, b);}}cout << sum - ans << endl;return 0;}