.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;
}
Автор: Антон Димитров
обратно към текущ брой
|