GONDOR - GONDOR
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
#include <cmath>
//#include <conio.h>
#include <iostream>
#define max 10000000
using namespace std;
struct diem
{
int x,y;
};
int n,so[110],a[110][110],flag[110];
diem d[110];
double f[110];
double min(double a,double b) { return a<b?a:b; }
double kc(diem A,diem B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int main()
{
//freopen("gondor.in.10","r",stdin);
f[1] = 0;
scanf("%d",&n);
for(int i = 2;i<=n;i++)
f[i] = max;
for(int i = 1;i<=n;i++)
{
scanf("%d %d %d",&d[i].x,&d[i].y,&so[i]);
for(int j = 1;j<=n-1;j++)
scanf("%d",&a[i][j]);
}
memset(flag,0,sizeof(flag));
int u = 1,fl,danhdau; flag[1] = 1;
while(true)
{
int t = 0;
for(int i = 1;i<=n;i++)
{
if(!flag[a[u][i]])
{
t++;
f[a[u][i]]=min(f[a[u][i]],f[u]+kc(d[u],d[a[u][i]]));
if(t==so[u])
break;
}
}
fl = 1; double maxx = max;
for(int i = 1;i<=n;i++)
if(!flag[i] && f[i]<maxx)
{
fl = 0;
danhdau = i;
maxx = f[i];
}
if(fl)
break;
else
{
flag[danhdau] = 1;
u = danhdau;
}
// printf("%d\n",u);
}
for(int i = 1;i<=n;i++)
printf("%lf\n",f[i]);
//getch();
}