結果

問題 No.748 yuki国のお財布事情
ユーザー testestesttestestest
提出日時 2018-10-19 21:49:40
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 55 ms / 2,000 ms
コード長 992 bytes
コンパイル時間 202 ms
コンパイル使用メモリ 31,104 KB
実行使用メモリ 7,168 KB
最終ジャッジ日時 2024-04-29 15:40:39
合計ジャッジ時間 1,659 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 0 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 0 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 0 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 0 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 1 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 7 ms
5,376 KB
testcase_14 AC 12 ms
5,376 KB
testcase_15 AC 8 ms
5,376 KB
testcase_16 AC 25 ms
5,376 KB
testcase_17 AC 48 ms
6,144 KB
testcase_18 AC 53 ms
6,784 KB
testcase_19 AC 55 ms
7,040 KB
testcase_20 AC 46 ms
6,528 KB
testcase_21 AC 50 ms
6,784 KB
testcase_22 AC 1 ms
5,376 KB
testcase_23 AC 1 ms
5,376 KB
testcase_24 AC 1 ms
5,376 KB
testcase_25 AC 45 ms
6,400 KB
testcase_26 AC 53 ms
7,040 KB
testcase_27 AC 53 ms
7,168 KB
testcase_28 AC 35 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'main':
main.c:19:9: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
   19 |         scanf("%d%d%d",&n,&m,&k);
      |         ^~~~~
main.c:1:1: note: include '<stdio.h>' or provide a declaration of 'scanf'
  +++ |+#include <stdio.h>
    1 | //union-find
main.c:19:9: warning: incompatible implicit declaration of built-in function 'scanf' [-Wbuiltin-declaration-mismatch]
   19 |         scanf("%d%d%d",&n,&m,&k);
      |         ^~~~~
main.c:19:9: note: include '<stdio.h>' or provide a declaration of 'scanf'
main.c:35:9: warning: implicit declaration of function 'qsort' [-Wimplicit-function-declaration]
   35 |         qsort(e,m,sizeof(E),edgehikaku);
      |         ^~~~~
main.c:46:9: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
   46 |         printf("%ld",ans);
      |         ^~~~~~
main.c:46:9: note: include '<stdio.h>' or provide a declaration of 'printf'
main.c:46:9: warning: incompatible implicit declaration of built-in function 'printf' [-Wbuiltin-declaration-mismatch]
main.c:46:9: note: include '<stdio.h>' or provide a declaration of 'printf'

ソースコード

diff # 

//union-find
#define LIMIT 100000
int uniroot[LIMIT+10],unicnt[LIMIT+10];
void ufinit(int n){for(int i=0;i<n;i++){uniroot[i]=i;unicnt[i]=1;}}
int root(int x){return uniroot[x]!=x?uniroot[x]=root(uniroot[x]):x;}
int same(int x,int y){return root(x)==root(y);}
void uni(int x,int y){if((x=root(x))==(y=root(y)))return;uniroot[x]=y;unicnt[y]+=unicnt[x];}

typedef struct edge{long s,g,c;}E;
int edgehikaku(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).c<(*q).c)return -1;
	return 1;
}

E e[100010];
int main(){
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	ufinit(n);
	for(int i=0;i<m;i++){
		long a,b,c;
		scanf("%ld%ld%ld",&a,&b,&c);
		e[i].s=a-1;
		e[i].g=b-1;
		e[i].c=c;
	}
	for(int i=0;i<k;i++){
		int t;
		scanf("%d",&t);
		t--;
		e[t].c=2000000000;
		uni(e[t].s,e[t].g);
	}
	qsort(e,m,sizeof(E),edgehikaku);
	
	long ans=0;
	for(int i=0;i<m;i++){
		if(same(e[i].s,e[i].g)){
			if(e[i].c==2000000000)break;
			ans+=e[i].c;
		}else{
			uni(e[i].s,e[i].g);
		}
	}
	printf("%ld",ans);
}
0