记录编号	346599	评测结果	AAAAAAAAAA
题目名称	P服务点设置	最终得分	100
用户昵称	O(1)	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2016-11-12 11:20:25	内存使用	0.21 MiB

#include<iostream>
#include<fstream>
#include<deque>
using namespace std;
int n,m,p,c[100][100],book[100];
int min_=99999999;
deque<int> s;
deque<int>::iterator it;
deque<int> a;
void dfs(int x,int deep)
{
	if(deep>p)
	   return;
	int i,max_=0,mmin=99999999;
	if(deep==p)
	{
		for(i=0;i<n;i++)
		{
			if(book[i]==0)
			{
				mmin=99999999;
				for(it=s.begin();it!=s.end();it++)
					if(c[i][*it]<mmin)
					  mmin=c[i][*it];
			    if(mmin>max_)
			      max_=mmin;
			}
		}
		//cout<<max_<<" "<<min_<<endl;
		if(max_<min_)
		{
			min_=max_;
			a.assign(s.begin(),s.end());
		}
		return;
	}
	for(i=x+1;i<n;i++)
	{
		book[i]=1;
		s.push_back(i);
		dfs(i,deep+1);
		book[i]=0;
		s.pop_back();											
	}
}
int main()
{
	ofstream fout("djsc.out");
	ifstream fin("djsc.in");
	fin>>n>>m>>p;
	int i,j,k,x,y,inf=99999999;
	for(i=0;i<n;i++)
	   for(j=0;j<n;j++)
	      if(i==j)  c[i][j]=0;
	      else      c[i][j]=inf;
	      
	for(i=0;i<m;i++)
	{
		fin>>k>>x>>y;
		c[k][x]=y;
		c[x][k]=y;
	}
	for(k=0;k<n;k++)
	   for(i=0;i<n;i++)
	      for(j=0;j<n;j++)
	         if(c[i][j]>c[i][k]+c[k][j])
	            c[i][j]=c[i][k]+c[k][j];        
	/*for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		    cout<<c[i][j]<<" ";
		cout<<endl;
	}*/
	for(i=0;i<n;i++)
	{
		book[i]=1;
		s.push_back(i);
		dfs(i,1);
		book[i]=0;
		s.pop_back();
	}
	for(it=a.begin();it!=a.end();it++)
	    fout<<*it<<" ";

}