結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
|
提出日時 | 2018-11-11 23:06:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 58 ms / 2,000 ms |
コード長 | 2,432 bytes |
コンパイル時間 | 1,856 ms |
コンパイル使用メモリ | 184,452 KB |
実行使用メモリ | 9,196 KB |
最終ジャッジ日時 | 2024-12-15 07:39:16 |
合計ジャッジ時間 | 3,444 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>#define FOR(v, a, b) for(int v = (a); v < (b); ++v)#define FORE(v, a, b) for(int v = (a); v <= (b); ++v)#define REP(v, n) FOR(v, 0, n)#define REPE(v, n) FORE(v, 0, n)#define REV(v, a, b) for(int v = (a); v >= (b); --v)#define ALL(x) (x).begin(), (x).end()#define LLI long long intusing namespace std;template <typename T> using V = vector<T>;template <typename T, typename U> using P = pair<T,U>;template <typename T, typename U> P<T,U> operator+(const P<T,U> &a, const P<T,U> &b){return {a.first + b.first, a.second + b.second};}template <typename T, typename U> P<T,U> operator-(const P<T,U> &a, const P<T,U> &b){return {a.first - b.first, a.second - b.second};}class UnionFind{vector<int> parent, depth, size;public:UnionFind(int n): parent(n), depth(n,1), size(n,1){REP(i, n) parent[i] = i;}int getRoot(int i){if(parent[i] == i) return i;else return parent[i] = getRoot(parent[i]);}bool isSame(int i, int j){return getRoot(i) == getRoot(j);}void merge(int i, int j){int ri = getRoot(i), rj = getRoot(j);if(ri != rj){if(depth[ri] < depth[rj]){parent[ri] = rj; size[rj] += size[ri];}else{parent[rj] = ri; size[ri] += size[rj];if(depth[ri] == depth[rj]) ++depth[ri];}}}int getSize(int i){return size[getRoot(i)];}};int N,M,K;vector<int> e;template <typename T>vector<tuple<int,int,T>> kruskal(int n, vector<tuple<int,int,T>> &graph){UnionFind uf(n);REP(i,K) uf.merge(get<0>(graph[e[i]]), get<1>(graph[e[i]]));vector<tuple<int,int,T>> mst;REP(i,K) mst.push_back(graph[e[i]]);sort(graph.begin(), graph.end(), [](tuple<int,int,T> &a, tuple<int,int,T> &b){return get<2>(a) < get<2>(b);});for(auto v : graph){int s,t,d;tie(s,t,d) = v;if(!uf.isSame(s,t)){uf.merge(s,t);mst.push_back(v);}}return mst;}int main(){cin.tie(0);ios::sync_with_stdio(false);cin >> N >> M >> K;vector<tuple<int,int,LLI>> graph;LLI cost = 0;REP(i,M){int a,b,c; cin >> a >> b >> c;graph.push_back(make_tuple(a-1,b-1,c));cost += c;}e.resize(K);REP(i,K){cin >> e[i]; e[i]--;}vector<tuple<int,int,LLI>> res = kruskal(N, graph);LLI ans = 0;REP(i,res.size()){//cout << get<0>(res[i]) << " " << get<1>(res[i]) << " " << get<2>(res[i]) << endl;ans += get<2>(res[i]);}cout << cost-ans << endl;return 0;}