結果

問題 No.748 yuki国のお財布事情
ユーザー testestesttestestest
提出日時 2018-10-19 21:49:40
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 64 ms / 2,000 ms
コード長 992 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 30,584 KB
実行使用メモリ 6,924 KB
最終ジャッジ日時 2023-08-12 00:49:08
合計ジャッジ時間 2,862 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 0 ms
4,380 KB
testcase_03 AC 0 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 0 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 0 ms
4,376 KB
testcase_12 AC 0 ms
4,376 KB
testcase_13 AC 8 ms
4,380 KB
testcase_14 AC 13 ms
4,376 KB
testcase_15 AC 10 ms
4,380 KB
testcase_16 AC 24 ms
4,376 KB
testcase_17 AC 58 ms
6,208 KB
testcase_18 AC 61 ms
6,660 KB
testcase_19 AC 62 ms
6,872 KB
testcase_20 AC 54 ms
6,420 KB
testcase_21 AC 60 ms
6,424 KB
testcase_22 AC 1 ms
4,380 KB
testcase_23 AC 1 ms
4,376 KB
testcase_24 AC 0 ms
4,380 KB
testcase_25 AC 55 ms
6,016 KB
testcase_26 AC 64 ms
6,924 KB
testcase_27 AC 62 ms
6,868 KB
testcase_28 AC 40 ms
4,984 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: 関数 ‘main’ 内:
main.c:19:9: 警告: 関数 ‘scanf’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   19 |         scanf("%d%d%d",&n,&m,&k);
      |         ^~~~~
main.c:1:1: 備考: include ‘<stdio.h>’ or provide a declaration of ‘scanf’
  +++ |+#include <stdio.h>
    1 | //union-find
main.c:19:9: 警告: 組み込み関数 ‘scanf’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
   19 |         scanf("%d%d%d",&n,&m,&k);
      |         ^~~~~
main.c:19:9: 備考: include ‘<stdio.h>’ or provide a declaration of ‘scanf’
main.c:35:9: 警告: 関数 ‘qsort’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   35 |         qsort(e,m,sizeof(E),edgehikaku);
      |         ^~~~~
main.c:46:9: 警告: 関数 ‘printf’ の暗黙的な宣言です [-Wimplicit-function-declaration]
   46 |         printf("%ld",ans);
      |         ^~~~~~
main.c:46:9: 備考: include ‘<stdio.h>’ or provide a declaration of ‘printf’
main.c:46:9: 警告: 組み込み関数 ‘printf’ の互換性がない暗黙的な宣言です [-Wbuiltin-declaration-mismatch]
main.c:46:9: 備考: 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