Тема: Алгоритм Дейкстры с помощью кучи
Можете написать Алгоритм Дейкстры с помощью кучи на языке Pascal
Re: Алгоритм Дейкстры с помощью кучи
Ну тут надо кучу написать 
Re: Алгоритм Дейкстры с помощью кучи
если интересно, то вот моя реализация Дейкстры, используя кучу STL.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int inf = 1000;
struct ind
{
int i, num;
};
bool operator < (const ind &a, const ind &b)
{
return a.num < b.num;
}
int e[101][101];
int n, s, f;
priority_queue < ind> d1;
bool g[101];
vector < int > d(101);
//ifstream cin("input.txt");
//ofstream cout("output.txt");
void dijkstra(int s1, int s2)
{
int i, j, bj, bd;
g[s1] = true;
for (i = 1; i <= n; i++){
d[i] = e[s1][i];
ind f;
f.i = i;
f.num = -e[s1][i];
d1.push(f);
}
for (i = 1; i < n; i++)
{
bj = -1;
bd = inf;
ind f;
f = d1.top();
/*bool gg = d1.empty();
if (g[f.i]){
while (g[f.i] && d1.empty() == false)
{
d1.pop();
f = d1.top();
}
}*/
d1.pop();
if (d1.empty()) break;
bj = f.i;
bd = -f.num;
if (bj == -1) break;
g[bj] = true;
for (j = 1; j <= n; j++)
if (bd + e[bj][j] < d[j])
{
d[j] = bd + e[bj][j];
f.i = j;
f.num = -d[j];
d1.push(f);
}
}
if (d[s2] == inf) cout << "-1";
else cout << d[s2];
}
int main()
{
cin >> n >> s >> f;
int i, j;
if (s == f){
cout << "0";
return 0;
}
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++){
int k;
cin >> k;
if (k == -1 || i == j) e[i][j] = inf;
else e[i][j] = k;
}
for (i = 1; i <= n; i++)
d[i] = inf;
dijkstra(s, f);
return 0;
}Re: Алгоритм Дейкстры с помощью кучи
Ну как минимум, можно упростить эту реализацию используя обычный pair<int,int> и чтобы не засовывать в кучу отрицательное расстояние используя обычный оператор <, лучше объявить ее так:
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > Q.Тогда просто
pair<int,int> a=make_pair(dist,num);
Q.push(a);Re: Алгоритм Дейкстры с помощью кучи
Хм, и действительно.
Спасибо, попробую так писать .
Re: Алгоритм Дейкстры с помощью кучи
черт, там человек на паскале просил)
Re: Алгоритм Дейкстры с помощью кучи
chum
Ага, на сях-то конечно легко Чтоб на Паскале написать, надо брать Кормена и реализовывать кучу, это несложный алгоритм. Ну или погуглить и найти готовый, но это не дзенно
Re: Алгоритм Дейкстры с помощью кучи
e-maxx
Да-да!:)))
Ну в конце концов можно писать RMQ, что, собственно, я и советую всем пишущим на паскале.
Когда, например, меня добъют сишные строки, я открываю делфи и, если нужно быстро искать минимум-максимум, пишу RMQ. Это просто и удобно:)
Кстати, умею находить минимум/максимум на отрезке [l; r] с помощью RMQ в 5 строчек)
Кто короче?:)
Re: Алгоритм Дейкстры с помощью кучи
Ну если просто находить максимум(т.е. только эта процедура), учитывая что обновление только в точке(как в данном случае), то что-то такое занимает немного места:
int findmax(int l,int r,int a,int b,int num)
{
if (l==a && b==r-1) return MAX[num];
if (b<(r+l)/2) return findmax(l,(r+l)/2,a,b,num*2); else
if (a>=(r+l)/2) return findmax((r+l)/2,r,a,b,num*2+1); else
return max(findmax(l,(r+l)/2,a,(r+l)/2-1,num*2),findmax((r+l)/2,r,(r+l)/2,b,num*2+1));
}Ищет максимум на отрезке [a,b]
Вызывать findmax(0,RANGE,a,b,1)
Re: Алгоритм Дейкстры с помощью кучи
кстати, можно в куче хранить не элементы, а индексы, ну и, разумеется, переопределить operator < на сравнение элементов в массиве d.
Re: Алгоритм Дейкстры с помощью кучи
Если нужно написать что - то на Паскале попросите у меня,я напишу. Если нужно кучу напишу,только отпишите ещё раз о помощи 
Re: Алгоритм Дейкстры с помощью кучи
А вы напишете эту же программу на Делфи?
Re: Алгоритм Дейкстры с помощью кучи
я могу выложить код на паскале, но только не с кучей, а с деревом отрезков.
Re: Алгоритм Дейкстры с помощью кучи
Вот полная реализация дерева отрезков Поиск суммы, минимум, кол-во минимум, модификация.
{r-,s-,q-,i-,o+}
{$r+,s+,q+,i+,o-}
uses math;
const Size=200000;
type dataTree=record l,r,a,min,s,c:longint; end;
var t:array[0..Size*3]of dataTree;
nz,n,_,minV,value,doit,l,r:longint;
procedure gen_tree(u,l,r:longint);
begin
t[u].l:=l; t[u].r:=r; t[u].min:=0;
t[u].a:=0; t[u].s:=0; t[u].c:=r-l+1;
if(l<r)then begin
gen_tree(u+u,l,(l+r) shr 1);
gen_tree(u+u+1,((l+r) shr 1)+1,r);
end;
end;
procedure modify(u,l,r:longint);
var x,y:longint;
begin
if(t[u].l=l)and(t[u].r=r)then inc(t[u].a,value) else begin
if(l<=t[u+u].r)then modify(u+u,l,min(t[u+u].r,r));
if(r>=t[u+u+1].l)then modify(u+u+1,max(l,t[u+u+1].l),r);
t[u].min:=min(t[u+u].min+t[u+u].a,t[u+u+1].min+t[u+u+1].a);
t[u].c:=0; x:=t[u+u].r-t[u+u].l+1; y:=t[u+u+1].r-t[u+u+1].l+1;
if(t[u].min=t[u+u].min+t[u+u].a)then inc(t[u].c,t[u+u].c);
if(t[u].min=t[u+u+1].min+t[u+u+1].a)then inc(t[u].c,t[u+u+1].c);
t[u].s:=t[u+u].a*x+t[u+u].s+t[u+u+1].a*y+t[u+u+1].s;
end;
end;
function fMin(u,l,r,w:longint):longint;
var res:longint;
begin
if(t[u].l=l)and(t[u].r=r)then begin
fMin:=w+t[u].min; exit;
end else begin
res:=maxlongint;
if(l<=t[u+u].r)then res:=min(res,fMin(u+u,l,min(t[u+u].r,r),w+t[u+u].a));
if(r>=t[u+u+1].l)then res:=min(res,fMin(u+u+1,max(l,t[u+u+1].l),r,w+t[u+u+1].a));
fMin:=res;
end;
end;
function fCout(u,l,r,w:longint):longint;
var res:longint;
begin
if(t[u].l=l)and(t[u].r=r)then begin
if(w+t[u].min=minV)then fCout:=t[u].c else fCout:=0;
exit;
end else begin
res:=0;
if(l<=t[u+u].r)then res:=res+fCout(u+u,l,min(t[u+u].r,r),w+t[u+u].a);
if(r>=t[u+u+1].l)then res:=res+fCout(u+u+1,max(l,t[u+u+1].l),r,w+t[u+u+1].a);
fCout:=res;
end;
end;
function fSum(u,l,r,w:longint):longint;
var res:longint;
begin
if(t[u].l=l)and(t[u].r=r)then begin
fSum:=(r-l+1)*w+t[u].s; exit;
end else begin
res:=0;
if(l<=t[u+u].r)then res:=res+fSum(u+u,l,min(t[u+u].r,r),w+t[u+u].a);
if(r>=t[u+u+1].l)then res:=res+fSum(u+u+1,max(l,t[u+u+1].l),r,w+t[u+u+1].a);
fSum:=res;
end;
end;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
read(nz,n);
gen_tree(1,1,n);
for _:=1 to nz do begin
read(doit,l,r);
if(doit=1)then begin // * Find Min (L .. R) * //
writeln(fMin(1,l,r,t[1].a));
end else
if(doit=2)then begin // * Find Sum (L .. R) * //
writeln(fSum(1,l,r,t[1].a))
end else
if(doit=3)then begin // * Find Kol-Min (L .. R) * //
minV:=fMin(1,l,r,t[1].a);
writeln(fCout(1,l,r,t[1].a));
end else
if(doit=4)then begin // * Add Value (L .. R)* //
read(value);
modify(1,l,r);
end else assert(0<>0);
end;
close(input);
close(output);
end.Re: Алгоритм Дейкстры с помощью кучи
А ведь можна и деревом Фенвика ,гораздо короче:)