Afişează mesaje
Pagini: [1]
1  infoarena - concursuri, probleme, evaluator, articole / Infoarena Monthly 2012 / Răspuns: Swaps2 : Martie 26, 2012, 18:29:25
sunt numar egal de 0 si 1?
2  infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Răspuns: 009 Algoritmul lui Dijkstra : Februarie 02, 2011, 20:55:19
Eu ma gandeam ca este ca la .campion...primul test este ca cel din exemplu shi ala imi dadea bine shi de asta...
Gata am rezolvat ms mult de help Smile
3  infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Răspuns: 009 Algoritmul lui Dijkstra : Februarie 01, 2011, 08:48:03
bine dar faza este ca mie imi afiseaza ce trebuie la primul exemplu dar imi zice ca e incorect shi imi ia 10 puncte pe la testu 7
http://infoarena.ro/job_detail/527540 asta e mesajul de la evaluator Brick wall
4  infoarena - concursuri, probleme, evaluator, articole / Arhiva educationala / Răspuns: 009 Algoritmul lui Dijkstra : Ianuarie 31, 2011, 20:50:43
imi poate spune si mie cineva de ce imi da incorect pe acest cod daca rezultatul e la fel cu cel de la raspunsuri
Cod:
#include<fstream>
#include<cstdio>
#include<vector>
#include<utility>
#define ff it->first
#define ss it->second

using namespace std;
int n,m,a,b,c,d[50005],oo=500000000,h[50010],poz[50010],i,l,nod,dist;
void read(),solve(),percolate(int t),sift(int f);
vector <pair<int,int> > v[50010];


int main()
{

read();
solve();
return 0;
}
void read()
{
ifstream in("dijkstra.in");
in>>n>>m;
for(;m;m--)
{
in>>a>>b>>c;
v[a].push_back(make_pair(b,c));
}
in.close();
}
void solve()
{
vector<pair<int,int> >::iterator it;
ofstream out("dijkstra.out");
for(i=1;i<=n;i++)
{
h[i]=i;
d[i]=oo;
poz[i]=i;
}
d[1]=0;
l=n;
for(;l;)
{
nod=h[1];
dist=d[nod];
for(it=v[nod].begin();it!=v[nod].end();it++)
if(d[ff]>dist+ss)
{
d[ff]=dist+ss;
percolate(poz[ff]);
}
h[1]=h[l];
poz[h[1]]=1;
l--;
sift(1);
}
for(i=2;i<=n;i++)
{
if(d[i]==oo)
d[i]=0;
}
for(i=2;i<=n;i++)
out<<d[i]<<" ";
out.close();
}
void percolate(int f)
{
int t,aux;
for(;;)
{
t=f>>1;
if(d[h[t]]<=d[h[f]])
return;
aux=h[t];
h[t]=h[f];
h[f]=aux;
poz[h[t]]=t;
poz[h[f]]=f;
f=t;
}
}
void sift(int t)
{
int f,aux;
for(;;)
{
f=t<<1;
if(f>l)
return;
if(f<l)
if(d[h[f]]<d[h[f+1]])
f++;
if(d[h[t]]<=d[h[f]])
return;
aux=h[t];
h[t]=h[f];
h[f]=aux;
poz[h[t]]=t;
poz[h[f]]=f;
t=f;
}
}
Pagini: [1]
Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines