USACO квалификационен кръг - октомври, GOLD Division, Задача cowski
Уловието на задачата може да прочетете
тук.
Решение
За тази задача е важно наблюдението, че по какъвто и път да
достигнем до дадена клетка скоростта, когато сме там, ще е винаги една и съща. Началната
клетка е с координати (0,0)и началната скорост е V. За дадена клетка с координати (x,y)скоростта в нея ще еV*2H(0,0)
- H(x,y). Тук H(x,y)показва височината на дадена клетка. По
какъвто и път да минем, за да достигнем дадена клетка скоростта в нея ще е една
и съща.
Така мрежата може да се представи като граф, в който всеки
връх има максимално 4 излизащи от
него ребра. За да се намери най-бързият път от горния ляв ъгъл до долния десен
може да се използва алгоритъма на Дийкстра. Върховете в графа могат да бъдат
максимално 10000, тъй като мрежата е
с максимална големина 100x100. Следователно трябва да се използва
пирамида при имплементацията на алгоритъма, за да се постигне по-добро време на
изпълнение. Тогава сложността е O(M*logN), като Mе броят на ребрата, а Nса върховете в графа.
Примерна реализация
# include <stdio.h>
# include <float.h>
# include <math.h>
# include <stdlib.h>
# define MAXN 128
# define MAXH 64
long double sp;
long double dist[MAXN][MAXN]; //Min time required to reach.
char used[MAXN][MAXN]; //Is the min time callculated
int n,m,tb[MAXN][MAXN],h0; //Number of Rows and Cowums,
//heights, initial height
int indx[4] = {-1,0,1,0}; //Used for easy move left, up, right, down
int indy[4] = {0,1,0,-1};
struct node{
int x,y;
};
node h[MAXN*MAXN]; //Heap
int hlen=0; //Heap len
int hpos[MAXN][MAXN]; //Position of an element in the heap
/* HEAP */
//Sifting a element up
void siftup(int p) {
int pp = (p-1)/2;
node buf = h[p];
while ( p!=0 && dist[buf.x][buf.y] <
dist[h[pp].x][h[pp].y] ) {
h[p] = h[pp];
hpos[h[p].x][h[p].y] = p;
p = pp;
pp = (p-1)/2;
}
h[p] = buf;
hpos[h[p].x][h[p].y] = p;
}
//Ads new element
void push(int a, int b) {
h[hlen].x = a;
h[hlen].y = b;
hpos[a][b] = hlen;
hlen++;
if ( hlen>1 )
siftup(hpos[a][b]);
}
//Sifting a element down
void siftdown(int p) {
int pp=2*p+1;
node buf=h[p];
while ( pp+1<hlen &&
( dist[h[pp].x][h[pp].y]<dist[buf.x][buf.y] ||
dist[h[pp+1].x][h[pp+1].y]<dist[buf.x][buf.y] )) {
if ( dist[h[pp].x][h[pp].y]<dist[h[pp+1].x][h[pp+1].y] ) {
h[p] = h[pp];
hpos[h[p].x][h[p].y] = p;
p = pp;
pp = 2*p+1;
} else {
h[p] = h[pp+1];
hpos[h[p].x][h[p].y] = p;
p = pp+1;
pp = 2*p+1;
}
}
while ( pp<hlen && dist[h[pp].x][h[pp].y]<dist[buf.x][buf.y] ) {
h[p] = h[pp];
hpos[h[p].x][h[p].y] = p;
p = pp;
pp = 2*p+1;
}
h[p] = buf;
hpos[h[p].x][h[p].y] = p;
}
//Get an element from the top of the Heap
node pop() {
node res;
if ( hlen==0 ) {
res.x = n; res.y = m;
} else {
res = h[0];
hpos[res.x][res.y] = -1;
if ( hlen>1 ) {
h[0] = h[--hlen];
siftdown(0);
}
}
return res;
}
/* END */
//Reads Input
void readf() {
freopen("cowski.in","r",stdin);
freopen("cowski.out","w",stdout);
scanf("%llg %d %d",&sp,&n,&m);
for ( int i=0 ; i<=n+1 ; i++ )
for ( int j=0 ; j<=m+1 ; j++ )
tb[i][j] = 1000;
for ( int i=1; i<=n ; i++ ) {
for ( int j=1 ; j<=m ; j++ ) {
scanf("%d",&tb[i][j]);
}
}
}
//Dijkstra Algorithm
long double dijkstra() {
//Init
for ( int i=0 ; i<MAXN ; i++ )
for ( int j=0 ; j<MAXN ; j++ ) {
dist[i][j] = LDBL_MAX;
used[i][j] = 0;
hpos[i][j] = -1;
}
h0 = tb[1][1];
dist[1][1] = 0;
used[1][1] = 1;
int nextx,nexty,nexth;
long double t;
nextx = 1, nexty = 1, nexth = h0;
//End of Init
do {
used[nextx][nexty] = 1;
for ( int i=0 ; i<4 ; i++ ) {
if ( tb[nextx+indx[i]][nexty+indy[i]]==1000 )
continue;
t = 1.0/(sp*pow(2.0,h0-tb[nextx][nexty]));
if ( used[nextx+indx[i]][nexty+indy[i]] == 0 &&
dist[nextx+indx[i]][nexty+indy[i]] >
dist[nextx][nexty]+t ) {
dist[nextx+indx[i]][nexty+indy[i]] =
dist[nextx][nexty]+t;
if ( hpos[nextx+indx[i]][nexty+indy[i]]==-1 ) {
push(nextx+indx[i],nexty+indy[i]);
} else {
siftup(hpos[nextx+indx[i]][nexty+indy[i]]);
}
}
}
node pp;
pp = pop();
nextx = pp.x; nexty = pp.y;
}while( nextx!=n || nexty!=m);
return dist[n][m];
}
int main() {
readf();
printf("%.2llf\n",dijkstra());
return 0;
}
Автор: Никола Борисов
обратно към текущ брой
|