結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2018-10-19 21:58:06 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 49 ms / 2,000 ms |
コード長 | 1,484 bytes |
コンパイル時間 | 665 ms |
コンパイル使用メモリ | 67,396 KB |
実行使用メモリ | 9,816 KB |
最終ジャッジ日時 | 2024-11-18 20:33:23 |
合計ジャッジ時間 | 2,362 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:68:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 68 | scanf("%d %d %d", &n, &m, &k); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:70:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 70 | scanf("%d %d %lld", &a[i], &b[i], &c[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:76:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 76 | scanf("%d", &x); | ~~~~~^~~~~~~~~~
ソースコード
#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#include<functional>#include<vector>#include<queue>#include<stack>#include<set>using namespace std;#define MOD 1000000007#define f(i,n) for(int i=0;i<int(n);i++)#define N 200000int p[N];int d[N];void init(void){f(i, N){p[i] = i;d[i] = 1;}return;}int pa(int x){if (p[x] == x)return x;else return p[x] = pa(p[x]);}void uni(int x, int y){int px = pa(x);int py = pa(y);if (px == py)return;if (d[px] < d[py]){p[px] = py;d[py] = max(d[py], d[px] + 1);}else{p[py] = px;d[px] = max(d[px], d[py] + 1);}return;}bool jud(int x, int y){int px = pa(x);int py = pa(y);if (px == py)return true;else return false;}int main(){int n,m,k;int x, y, z;int a[N];int b[N];long long c[N];bool used[N];long long s, ans;bool v = true;vector < pair<long long, pair<int, int> > >pe;ans = 0;init();scanf("%d %d %d", &n, &m, &k);f(i, m){scanf("%d %d %lld", &a[i], &b[i], &c[i]);a[i]--;b[i]--;used[i] = false;}f(i, k){scanf("%d", &x);x--;used[x] = true;uni(a[x], b[x]);}f(i, m){if (!used[i]){pe.push_back(make_pair(c[i], make_pair(a[i], b[i])));}}sort(pe.begin(), pe.end());f(i, pe.size()){if (jud(pe[i].second.first, pe[i].second.second)){ans += pe[i].first;}else{uni(pe[i].second.first, pe[i].second.second);}}printf("%lld\n", ans);return 0;}