比赛 防止浮躁的小练习V0.1 评测结果 AAAAAAAAAA
题目名称 P服务点设置 最终得分 100
用户昵称 NVIDIA 运行时间 0.027 s
代码语言 C++ 内存使用 0.36 MiB
提交时间 2016-10-07 17:39:42
显示代码纯文本
#include<bits/stdc++.h>
#define QMAX 99999999
using namespace std;
int i,j,k,m,u,v,w;
int dis[105][105], n, p, jg[105], t[105], Max;
void dfs(int x,int num)
{int i, j;
if(num==p)
{
	int Max1 = 0,Max2;
		for (i = 0; i < n; i++)
		{
			Max2 = dis[t[0]][i];
			for (j = 1; j < p; j++){if (Max2>dis[t[j]][i]){Max2 = dis[t[j]][i];}}
            if (Max2 >= Max){break;}
            if (Max2 > Max1){Max1 = Max2;}
		}
if(i==n){Max = Max1;
		for(i=0;i<p;i++){jg[i] = t[i];}}
		return;
	}
if(x == n){return;}
for(i=x;i<n;i++){
		t[num]=i;
		dfs(x+1,num+1);}
return;
}
int main()
{
	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++){dis[i][j]=QMAX;}
		dis[i][i]=0;
	}
for (i = 0;i<m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
        dis[u][v] = w;
		dis[v][u] = w;
	}
   for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			for (k = 0; k < n; k++)
			{
				if (dis[i][k]+dis[k][j]<dis[i][j])
				{
					dis[i][j]=dis[i][k]+dis[k][j];
				}
			}
		}
	}
Max=QMAX;
dfs(0,0);
for (i = 0; i < p; i++){printf("%d ",jg[i]);}
	printf("\n");
return 0;
}