记录编号	45878	评测结果	AAAAAAAAAA
题目名称	P服务点设置	最终得分	100
用户昵称	青阳	是否通过	通过
代码语言	C	运行时间	0.037 s
提交时间	2012-10-25 19:50:41	内存使用	0.30 MiB

#include <stdio.h>
#define min(a, b) ((a)<(b)?(a):(b))
#define INF 0x7FFFFF
int map[100][100];
int tmp[100], ans[101];
int m, n, p;

void srch(int start, int now)
{
	int i, j;
	if(now >= p){
		int t, s;
		t = 0;
		for(i = 0; i < n; i++){
		      	s = INF;
			for(j = 0; j < now; j++){
				s = min(map[tmp[j]][i], s);
			}
			if(t < s){
				t = s;
			}
		}
		if(ans[n] > t){
			ans[n] = t;
			for(i = 0; i < now; i++){
				ans[i] = tmp[i];
			}
		}
		return ;
	}
	for(i = start; i < n; i++){
		tmp[now] = i;
		srch(i + 1, now + 1);
	}
	tmp[now] = 0;
}

int main(void)
{
	int i, j, k;
	int a, b, c;
	freopen("djsc.in", "r", stdin);
	freopen("djsc.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &p);
	for(i = 0; i < n; i++){
		for(j = 0; j < n; j++){
			map[i][j] = INF;
		}
		map[i][i] = 0;
	}
	for(i = 0; i < m; i++){
		scanf("%d%d%d", &a, &b, &c);
		map[a][b] = map[b][a] = c;
	}
	for(k = 0; k < n; k++){
		for(i = 0; i < n; i++){
			for(j = i + 1; j < n; j++){
				if(map[i][j] > map[i][k] + map[k][j]){
					map[i][j] = map[i][k] + map[k][j];
				}
			}
		}
	}
	ans[n] = INF;
	srch(0, 0);
	for(i = 0; i < p; i++){
		if(i != 0){
			printf(" ");
		}
		printf("%d", ans[i]);
	}
	printf("\n");
	return 0;
}