记录编号	289681	评测结果	AAAAAAAAAA
题目名称	P服务点设置	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-08-05 13:52:14	内存使用	0.33 MiB

#include<cstdio>
#include<cstring>
#include<cassert>
const int maxn=105;
int n,m,p;
int dis[maxn][maxn];
int min(int a,int b){
	return a<b?a:b;
}
int max(int a,int b){
	return a>b?a:b;
}
int best[maxn];int ans=0x7fffffff;
int sol[maxn];int tot;
bool better(){
	int now=0,tmp;
	for(int i=1;i<=n;++i){//枚举村庄 
		tmp=0x7fffffff;
		for(int j=1;j<=p;++j){
			tmp=min(tmp,dis[sol[j]][i]);
		} 
		now=max(now,tmp);
		if(now>=ans)return false;
	}
	if(now<ans){
		ans=now;
		return true;
	}else return false;
}
void dfs(int x){
	if(tot==p){
		if(better())memcpy(best,sol,sizeof(sol));
		return;
	}
	for(int i=x;n-i+1>=p-tot;++i){//还需p-tot,最多能选n-i+1个 
		sol[++tot]=i;
		dfs(i+1);
		--tot;
	}
}
int main(){
	freopen("djsc.in","r",stdin);
	freopen("djsc.out","w",stdout);
	memset(dis,63,sizeof(dis));
	scanf("%d %d %d",&n,&m,&p);
	int a,b,c;
	while(m--){
		scanf("%d %d %d",&a,&b,&c);a++;b++;
		dis[a][b]=dis[b][a]=min(dis[b][a],c);
	}
	for(int i=1;i<=n;++i)dis[i][i]=0;
	for(int k=1;k<=n;++k){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(dis[i][k]+dis[k][j]<dis[i][j])dis[i][j]=dis[i][k]+dis[k][j];
			}
		}
	}
	dfs(1);
	printf("%d",best[1]-1);
	for(int i=2;i<=p;++i)printf(" %d",best[i]-1);
	printf("\n");
	fclose(stdin);fclose(stdout);
	return 0;
}
/*
9
8
3
0 1 2
1 2 3
2 3 3
3 4 1
4 5 3
5 6 2
6 7 1
7 8 3
4
0 3 6
*/