結果

問題 No.748 yuki国のお財布事情
ユーザー matsukin1111matsukin1111
提出日時 2019-02-19 21:53:20
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 135 ms / 2,000 ms
コード長 2,016 bytes
コンパイル時間 1,027 ms
コンパイル使用メモリ 105,672 KB
実行使用メモリ 11,468 KB
最終ジャッジ日時 2024-04-20 23:07:01
合計ジャッジ時間 3,892 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 16 ms
6,940 KB
testcase_14 AC 28 ms
6,940 KB
testcase_15 AC 19 ms
6,944 KB
testcase_16 AC 52 ms
6,944 KB
testcase_17 AC 104 ms
8,140 KB
testcase_18 AC 119 ms
10,432 KB
testcase_19 AC 135 ms
11,468 KB
testcase_20 AC 122 ms
10,704 KB
testcase_21 AC 121 ms
9,544 KB
testcase_22 AC 2 ms
6,944 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,940 KB
testcase_25 AC 93 ms
8,140 KB
testcase_26 AC 116 ms
9,160 KB
testcase_27 AC 110 ms
8,656 KB
testcase_28 AC 95 ms
10,452 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <typeinfo>
#include <utility> 

#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;

struct edge { ll to; ll from; ll cost; };
bool comp(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}


ll V, E;


class UnionFind {
public:
	vector<int> r, p;

	UnionFind() {}
	UnionFind(int size) {
		r.resize(size, 0);
		p.resize(size, 0);
		rep(i, 0, size)makeSet(i);
	}

	void makeSet(int x) {
		p[x] = x;
		r[x] = 0;
	}

	bool same(int x, int y) {
		return findSet(x) == findSet(y);
	}

	void unite(int x, int y) {
		link(findSet(x), findSet(y));
	}

	void link(int x, int y) {
		if (r[x] > r[y]) {
			p[y] = x;
		}
		else {
			p[x] = y;
			if (x == y) {
				r[y]++;
			}
		}
	}


	int findSet(int x) {
		if (x == p[x]) {
			return x;
		}
		else {
			return p[x] = findSet(p[x]);
		}
	}
};



ll kruskal(vector<edge>edges,vector<pair<ll,ll>>should_unite) {
	sort(edges.begin(), edges.end(),comp);
	UnionFind un = UnionFind(V);
	rep(i, 0, should_unite.size()) {
		un.unite(should_unite[i].first,should_unite[i].second);
	}
	ll res = 0;
	rep(i, 0, edges.size()) {
		edge e = edges[i];
		if (!un.same(e.from, e.to)) {
			un.unite(e.from, e.to);
			res += e.cost;
		}
	}
	return res;
}

int main() {
	int K;
	cin >> V >> E >> K;
	vector<edge>edges;
	vector<pair<ll,ll>>should_unite;
	ll sum_1 = 0LL;
	ll sum_2 = 0LL;

	rep(i, 0, E) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		sum_1 += c;
		edges.push_back({a,b,c});
	}

	rep(i, 0, K) {
		ll e;
		cin >> e;
		e--;
		sum_2 += edges[e].cost;
		should_unite.push_back({edges[e].from,edges[e].to});
	}

	cout << sum_1 - sum_2 - kruskal(edges, should_unite) << endl;

}
0