結果

問題 No.748 yuki国のお財布事情
ユーザー roarisroaris
提出日時 2019-11-21 19:42:35
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 1,967 bytes
コンパイル時間 1,878 ms
コンパイル使用メモリ 180,988 KB
実行使用メモリ 11,064 KB
最終ジャッジ日時 2024-10-10 22:42:52
合計ジャッジ時間 3,637 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:85:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   85 |     for (auto& [ai, bi, ci] : edges) {
      |                ^

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef tuple<int, int, int> T;
struct Unionfind {
vector<int> par, rank;
Unionfind(int n) {
par.resize(n);
fill(par.begin(), par.end(), -1);
rank.resize(n);
fill(rank.begin(), rank.end(), 0);
}
int root(int x) {
if (par[x]<0) return x;
par[x] = root(par[x]);
return par[x];
}
void unite(int x, int y) {
int rx = root(x), ry = root(y);
if (rx==ry) return;
if (rank[rx]>=rank[ry]) {
par[rx] += par[ry];
par[ry] = rx;
if (rank[rx]==rank[ry]) {
rank[rx]++;
}
}
else {
par[ry] += par[rx];
par[rx] = ry;
}
}
int is_same(int x, int y) {
return root(x)==root(y);
}
int count(int x) {
return -par[root(x)];
}
};
signed main() {
cin.tie(0); ios::sync_with_stdio(false);
int N, M, K; cin >> N >> M >> K;
int a[M], b[M], c[M];
int cost_sum = 0;
for (int i=0; i<M; i++) {
cin >> a[i] >> b[i] >> c[i];
cost_sum += c[i];
}
int flag[M];
fill(flag, flag+M, 0);
for (int i=0; i<K; i++) {
int ei; cin >> ei;
flag[ei-1] = 1;
}
vector<T> edges;
Unionfind uf = Unionfind(N);
int cost = 0;
for (int i=0; i<M; i++) {
if (flag[i]) {
uf.unite(a[i]-1, b[i]-1);
cost += c[i];
}
else {
edges.push_back(make_tuple(a[i]-1, b[i]-1, c[i]));
}
}
sort(edges.begin(), edges.end(), [](T const t1, T const t2) {return get<2>(t1)<get<2>(t2);});
for (auto& [ai, bi, ci] : edges) {
if (!(uf.is_same(ai, bi))) {
uf.unite(ai, bi);
cost += ci;
}
}
cout << cost_sum-cost << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0