Pagini recente » Borderou de evaluare (job #203621) | Borderou de evaluare (job #1905870) | Cod sursa (job #1908698)
#include<cstdio>
#include<vector>
using namespace std;
int n,m;
vector< pair<int,int> > adj[50010];
int heap[50010],sz;
int res[50010];
int pos_in_heap[50010];
bool viz[50010];
void up_heap(int nod)
{
while(res[heap[nod/2]]>res[heap[nod]]&&nod>1)
{
swap(heap[nod/2],heap[nod]);
swap(pos_in_heap[heap[nod]],pos_in_heap[heap[nod/2]]);
up_heap(nod/2);
}
}
void down_heap(int nod)
{
while(nod*2<=sz)
{
if(nod*2+1<=sz)
{
if(res[heap[nod*2]]<res[heap[nod*2+1]])
{
if(res[heap[nod]]>res[heap[nod*2]])
{
swap(heap[nod],heap[nod*2]);
swap(pos_in_heap[heap[nod*2]],pos_in_heap[heap[nod]]);
down_heap(nod*2);
}
else
{
break;
}
}
else
{
if(res[heap[nod]]>res[heap[nod*2+1]])
{
swap(heap[nod],heap[nod*2+1]);
swap(pos_in_heap[heap[nod*2+1]],pos_in_heap[heap[nod]]);
down_heap(nod*2+1);
}
else
{
break;
}
}
}
else if(res[heap[nod]]>res[heap[nod*2]])
{
swap(heap[nod],heap[nod*2]);
swap(pos_in_heap[heap[nod*2]],pos_in_heap[heap[nod]]);
down_heap(nod*2);
}
else
{
break;
}
}
}
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d %d",&n,&m);
sz=1;
pos_in_heap[1]=1;
heap[1]=1;
res[1]=0;
for(int i=2;i<=n;i++)
{
res[i]=1000000001;
}
int x,y,c;
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&c);
pair<int,int> val(y,c);
adj[x].push_back(val);
}
//int lg=2;
while(sz>0)
{
//printf("***\n");
viz[heap[1]]=1;
for(vector< pair<int,int> >::iterator it=adj[heap[1]].begin();it!=adj[heap[1]].end();++it)
{
//printf("%d %d %d\n",heap[1],(*it).first,(*it).second);
if(viz[(*it).first]==0)
{
viz[(*it).first]=1;
sz++;
heap[sz]=(*it).first;
pos_in_heap[(*it).first]=sz;
res[(*it).first]=res[heap[1]]+(*it).second;
up_heap(pos_in_heap[(*it).first]);
}
else if(res[(*it).first]>res[heap[1]]+(*it).second)
{
res[(*it).first]=res[heap[1]]+(*it).second;
up_heap(pos_in_heap[(*it).first]);
}
/*lg=1;
for(int i=1;i<=sz;i++)
{
if(i==lg)
{
lg<<=1;
printf("\n");
}
printf("%d ",res[heap[i]]);
}
printf("\n");*/
}
//printf("\n");
pos_in_heap[heap[sz]]=1;
swap(heap[1],heap[sz]);
sz--;
down_heap(1);
}
for(int i=2;i<=n;i++)
{
if(res[i]==1000000001)
{
printf("0 ");
}
else
{
printf("%d ",res[i]);
}
}
}