记录编号	60885	评测结果	AAAAAAATTA
题目名称	P服务点设置	最终得分	80
用户昵称	宋S	是否通过	未通过
代码语言	C++	运行时间	6.375 s
提交时间	2013-05-31 19:48:49	内存使用	13.91 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define zero 1e-8
using namespace std;
int n,m,p;
typedef struct{int y,next,d;}node;
node e[21000];
int loc[210],top=0;
typedef struct{int sum,num,sum1;}node2;
node2 inv[210];
int a[200],b[200];
int flag[200];
int dist[110],q[300],flag1[110],front,rear;
bool cmp(node2 a,node2 b)
{return (a.sum*a.sum1)>(b.sum*b.sum1);}

inline void linkk(int x,int y,int d)
{
  e[++top].y=y;
  e[top].d=d;
  e[top].next=loc[x];
  loc[x]=top;
}

inline void init()
{
  int x,y,d;
  scanf("%d %d %d",&n,&m,&p);
  for (int i=0; i<n; ++i)
    inv[i].num=i;
  for (int i=1; i<=m; ++i)
    {
      scanf("%d %d %d",&x,&y,&d);
      linkk(x,y,d);
      linkk(y,x,d);
      inv[x].sum++;
      inv[y].sum++;
      inv[x].sum1+=d;
      inv[y].sum1+=d;
    }
  sort(inv,inv+n,cmp);
}
  
inline bool relax(int x,int i)
{
  if (dist[x]+e[i].d<dist[e[i].y])
    {
      dist[e[i].y]=dist[x]+e[i].d;
      return 1;
    }return 0;
}
  
inline int check()
{
  int x;
  memset(dist,63,sizeof(dist));
  memset(flag1,0,sizeof(flag1));
  memset(q,0,sizeof(q));
  front=0; rear=0;
  for (int i=0; i<p; ++i)
    { flag1[a[i]]=1; q[++rear]=a[i];dist[a[i]]=0;}
  while (front<rear)
    {
      flag1[x=q[++front]]=0;
      for (int i=loc[x];i;i=e[i].next)
        if ((relax(x,i)) && (!flag1[e[i].y]))
          flag1[q[++rear]=e[i].y]=1;
    }
  int max_=-1;
  for (int i=0; i<n; ++i) max_=max(max_,dist[i]);
  return max_;
}
  
inline bool check2()
{
  sort(a,a+p); sort(b,b+p);
  for (int i=0; i<p; ++i)
    if (a[i]!=b[i]) return a[i]<b[i];
}
  
inline void work()
{
  for (int i=0; i<p; ++i)
    a[i]=inv[i].num,flag[a[i]]=1;
  int last,ans,best,loc1,x1,x2;
  double t=10000000,t0=10000,tmin=0.05,k=0.9994,p1;
  last=best=check();
  memcpy(b,a,sizeof(b));
  while (t>tmin)
    { 
      loc1=rand()%p;
      x1=a[loc1];
      x2=rand()%n; while (flag[x2]) x2=rand()%n;
      flag[x1]=0; flag[x2]=1;
      a[loc1]=x2;
      ans=check();
      if (ans<=last) 
        {
          last=ans;
          if ((ans<best) || ((ans==best) && (check2())))
            {
              best=ans;
              memcpy(b,a,sizeof(b));
            }
        }else
        {
          p1=(double)(rand()%10000)/10000;
          if (exp((double)(last-ans)/t)>p1)
            last=ans;else
          {
            flag[x1]=1; flag[x2]=0;
            a[loc1]=x1;
          }
        }
      t*=k;
    }
  sort(b,b+p);
  for (int i=0; i<p; ++i)
    cout<<b[i]<<' ';
  cout<<endl;
}

int main()
{
  freopen("djsc.in","r",stdin);
  freopen("djsc.out","w",stdout);
  init();
  work();
  return 0;
}