結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
|
提出日時 | 2018-10-19 22:59:37 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 1,909 bytes |
コンパイル時間 | 833 ms |
コンパイル使用メモリ | 67,812 KB |
実行使用メモリ | 9,676 KB |
最終ジャッジ日時 | 2024-11-18 22:11:47 |
合計ジャッジ時間 | 3,536 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<iostream>#include<string>#include<iomanip>#include<algorithm>using namespace std;#define int long long#define rep(i,n) for(int i = 0; i < n; i++)#define INF (long long)(1e17)#define MOD (int)(1e9+7)#define min(a,b) (a>b?b:a)#define max(a,b) (a>b?a:b)#define yn(f) (f?"Yes":"No")#define YN(f) (f?"YES":"NO")#define pro "はいプロ 世界一○○が上手 ○○界のtourist ○○時代の終焉を告げる者 実質○○ ○○するために生まれてきた男"#define Answer_to_the_Ultimate_Question_of_Life_the_Universe_and_Everything 42#define MAX_E 100005#define MAX_V 100005#define MAX 100005struct edge{int u, v, cost;};bool comp(const edge& e1, const edge& e2){return e1.cost < e2.cost;}int V, E, K;edge es[MAX_E];int par[MAX_V];int _rank[MAX_V];int a[MAX], b[MAX], c[MAX];void init(int x){for(int i = 0; i < x; i++){par[i] = i;_rank[i] = 0;}}int find(int x){return par[x] == x ? x : par[x] = find(par[x]);}void unite(int x, int y){x = find(x);y = find(y);if(_rank[x] < _rank[y]){par[x] = y;} else{par[y] = x;if(_rank[x] == _rank[y]) _rank[x]++;}}bool same(int x, int y){return find(x) == find(y);}int kruskal(){sort(es, es + E, comp);// init(V);int res = 0, count = 0;// for(int i = 0; i < E && count != V-1; i++){for(int i = 0; i < E; i++){edge e = es[i];if(!same(e.u, e.v)){unite(e.u,e.v);res += e.cost;count++;}}return res;}signed main(){int s, t, w, e, ans = 0, sum = 0, kr;cin>>V>>E>>K;for(int i = 0; i < E; i++){cin>>s>>t>>w;es[i].u = s;es[i].v = t;es[i].cost = w;a[i]=s;b[i]=t;c[i]=w;sum += w;}init(V);for(int i = 0; i < K; i++){cin>>e;unite(a[e-1],b[e-1]);ans += c[e-1];// es[e].cost = INF;}kr = kruskal();// cout<<sum<<" "<<ans<<" "<<kr<<endl;cout<<sum-(ans+kr)<<endl;return 0;}