結果
問題 | No.748 yuki国のお財布事情 |
ユーザー |
![]() |
提出日時 | 2018-10-19 21:38:31 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 1,035 bytes |
コンパイル時間 | 220 ms |
コンパイル使用メモリ | 31,872 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-18 20:13:30 |
合計ジャッジ時間 | 1,803 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<stdio.h>#include<stdlib.h>typedef long long int int64;typedef struct wedge{int a,b,c;} edge;int root(int *u,int x){if(u[x]==x) return x;return u[x]=root(u,u[x]);}int same(int *u,int x,int y){return root(u,x)==root(u,y);}void unite(int *u,int x,int y){x=root(u,x);y=root(u,y);if(x==y) return;u[x]=y;}int cmp(const void *a,const void *b){return (*(edge *)a).c-(*(edge *)b).c;}void run(void){int n,m,k;scanf("%d%d%d",&n,&m,&k);edge *e=(edge *)calloc(m,sizeof(edge));int i;for(i=0;i<m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);int *u=(int *)calloc(n+1,sizeof(int));for(i=0;i<=n;i++) u[i]=i;for(i=0;i<k;i++){int p;scanf("%d",&p);p--;unite(u,e[p].a,e[p].b);e[p].c=0;}qsort(e,m,sizeof(edge),cmp);int64 sum=0;for(i=0;i<m;i++){if(e[i].c==0) continue;if(same(u,e[i].a,e[i].b)){sum+=e[i].c;} else {unite(u,e[i].a,e[i].b);}}printf("%lld\n",sum);}int main(void){run();return 0;}