Текущ брой на Списание ИнфоМан
 


.campion - 2 кръг - Задача zmeu

Уловието на задачата може да прочетете тук.

Решение

Пътят на принца задължително започва от клетката, в която е поставен той в началото и завършва в клетка, в която има изход. Важно е в какъв ред той обхожда клетките, в които са момичетата. Момичетата са 5 на брой. Броят на различните последователности, в които принца може да обходи клетките на момичетата е 5!. Ако са известни най-кратките пътища между клетките, в които са дъщерите и освен това за всяка дъщеря е пресметнато коя е най-близката клетка с изход могат да се проверят всички обхождания и да се избере най-доброто от тях.

За да се пресметне тази информация може да се използва алгоритъмът на Дейкстра. С негова помощ могат да се пресметнат най-кратките разстояния от принца до всяко от момичетата и между всеки две момичета. Също има информация за най-близката клетка с изход за всяко едно момиче. Алгоритъмът на Дейкстра може да се реализира със сложност O(N2). Няма реална полза от реализиране на алгоритъма с двоична пирамида тъй като сложността O(M*logN) може да е по-лоша от квадратната. Това е така, понеже графът може да е пълен.

Съществува и решение, при което се “разширява” графът. Така на всеки връх ще съответстват 25 върха, всеки от които описва кои от клетките с момичета са обходени до момента. Така, когато принцът е в дадена клетка се знае кои от дъщерите са били посетени до момента и на кои предстои да бъдат посетени. Накрая отговорът е в някой от подвърховете, които имат изход и са с код, обозначаващ, че всички момичета са посетени. С това разширяване на графа върховете стават 32*N и скоростта при използване на алгоритъма на Дейкстра е по-лоша от тази на описания по-горе алгоритъм.

Примерна реализация


#include <stdio.h>
#include <string.h>

#define INP             "zmeu.in"
#define OUT             "zmeu.out"

#define MAXN            1008

#define INF             2000000000

int n,m,p;
int prince;
int pr[5];
int matr[MAXN][MAXN];
int endc[MAXN];
int distpr[5];
int prm[5][5];
int vis[MAXN];
int dist[MAXN];
int perm[5];
int used[5];
int clexit[5];
int ans;

void input()
{
       FILE *f;

       int i;
       int a,b,w;

       memset(endc,0,sizeof(endc));

       f = fopen(INP,"r");

       fscanf(f,"%d %d %d",&n,&m,&p);
       fscanf(f,"%d",&prince);
       for(i=0;i<5;i++)
               fscanf(f,"%d",&pr[i]);
       for(i=0;i<m;i++)
       {
               fscanf(f,"%d %d %d",&a,&b,&w);
               matr[a][b] = w;
               matr[b][a] = w;
       }
       for(i=0;i<p;i++)
       {
               fscanf(f,"%d",&a);
               endc[a] = 1;
       }

       fclose(f);
}

void dijkstra(int node)
{
       int i;
       int min,mind;

       for(i=0;i<MAXN;i++)
       {
               vis[i] = 0;
               dist[i] = INF;
       }

       dist[node] = 0;

       while(1)
       {
               min = INF;
               mind = -1;
               for(i=1;i<=n;i++)
                       if(!vis[i] && dist[i]<min)
                       {
                               min = dist[i];
                               mind = i;
                       }

               if(mind==-1)
                       break;

               vis[mind] = 1;

               for(i=1;i<=n;i++)
                       if(matr[mind][i])
                               if(dist[mind]+matr[mind][i]<dist[i])
                                       dist[i] = dist[mind]+matr[mind][i];
       }
}

void checkAns()
{
       int i;
       int tans;

       tans = distpr[perm[0]];
       for(i=0;i<4;i++)
               tans += prm[perm[i]][perm[i+1]];
       tans += clexit[perm[4]];

       if(ans>tans)
               ans = tans;
}

void rec(int lev)
{
       int i;

       if(lev==5)
       {
               checkAns();
               return;
       }

       for(i=0;i<5;i++)
               if(!used[i])
               {
                       perm[lev] = i;
                       used[i] = 1;
                       rec(lev+1);
                       used[i] = 0;
               }
}

void solve()
{
       int i,i2;

       dijkstra(prince);
       for(i=0;i<5;i++)
               distpr[i] = dist[pr[i]];

       for(i=0;i<5;i++)
       {
               dijkstra(pr[i]);
               for(i2=0;i2<5;i2++)
                       prm[i][i2] = dist[pr[i2]];
               clexit[i] = INF;
               for(i2=1;i2<=n;i2++)
                       if(endc[i2] && clexit[i]>dist[i2])
                               clexit[i] = dist[i2];
       }

       ans = INF;
       rec(0);
}

void output()
{
       FILE *f;

       f = fopen(OUT,"w");

       fprintf(f,"%d\n",ans);

       fclose(f);
}

int main()
{
       input();
       solve();
       output();

       return 0;
}



Автор: Антон Димитров


обратно към текущ брой