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();               
}

Download