讨论 / AC的过来看看
kingmew 2013-06-10 03:18:00
点我顶贴 收藏 删除
AC的都来看看

7

0 0

0 2

1 2

3 2

3 1

3 0

1 0

答案应为1 谁对了的?

#1 ggbbgg@2016-02-22 23:44:42
回复 删除
#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int INF = 1 << 29;

int n,tw,te;

//储存MST

int head[101],next[201],g[201];

double w[201];

//储存边

double e[10001];

int f[101];

int u[10001],v[10001];

int r[10001];

//储存点

double x[101],y[101];

bool vis[101][101];

//

double d[101];

bool mark[101];

double dis(int a,int b)

{

double i = (x[a]-x[b])*(x[a]-x[b]),j = (y[a]-y[b])*(y[a]-y[b]);

return sqrt(i+j);

}

int find(int i)

{

return (f[i]==i)?i:f[i]=find(f[i]);

}

bool cmp(const int& a,const int& b)

{

return e[a]<e[b];

}

void adde(int a,int b,double c)

{

w[tw]=c;

g[tw]=b;

next[tw]=head[a];

head[a]=tw++;

}

int main()

{

scanf("%d",&n);

for(int i = 1;i <= n;++i)

scanf("%lf%lf",&x[i],&y[i]),f[i]=i;

for(int i = 1;i <= n;++i)

{

for(int j = 1;j <= n;++j)

if(!vis[i][j]){

e[te]=dis(i,j);

u[te]=i;v[te]=j;

r[te]=te++;

vis[j][i]=true;

}

}

sort(r,r+te,cmp);

memset(head,-1,sizeof(head));

//MST

int cnt = n-1;

double ans(0);

for(int i = 0;i < te&&cnt;++i)

{

int j = r[i];

int fx=find(u[j]),fy=find(v[j]);

if(fx!=fy)

{

f[fx]=fy;

ans+=e[j];

--cnt;

adde(u[j],v[j],e[j]);

adde(v[j],u[j],e[j]);

}

}

//1->n

for(int i = 2;i <= n;++i)d[i]=INF;

for(int i = 1;i <= n;++i)

{

double mi = INF;

int a;

for(int j = 1;j <= n;++j)if(d[j]<mi&&!mark[j])mi=d[a=j];

mark[a]=true;

for(int j = head[a];j != -1;j = next[j])

{

int k = g[j];

d[k]=min(d[k],d[a]+w[j]);

}

}

printf("%.2lf %.2lf",ans,d[n]);

return 0;

}

查看更多回复
提交回复