Pagini recente » Borderou de evaluare (job #1837830) | Cod sursa (job #2013055)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int,int> >v[50001];
int heap[50001],poz[50001],cost[50001],N ;
queue<int>q;
void sift(int nod)
{
if(2*nod<=N)
{
int son=2*nod;
if(son+1<=N&&cost[heap[son+1]]<cost[heap[son]])son++;
if(cost[heap[nod]]>cost[heap[son]])
{ int aux;
aux= heap[nod];
heap[nod]=heap[son];
heap[son]=aux;
poz[heap[nod]]=nod;
poz[heap[son]]=son;
nod=son;
son=2*nod;
while(son<=N)
{
if(son+1<=N&&cost[heap[son+1]]<cost[heap[son]])son++;
if(cost[heap[nod]]>cost[heap[son]])
{int aux;
aux= heap[nod];
heap[nod]=heap[son];
heap[son]=aux;
poz[heap[nod]]=nod;
poz[heap[son]]=son;
nod=son;
son=2*nod;
}
else return;
}
}
}return;
}
void percolate(int k)
{
int key,nod=heap[k];
key=k;
while(key>=2&&cost[nod]<cost[heap[key/2]])
{
heap[key]=heap[key/2];
poz[heap[key/2]]=key;
key=key/2;
}
heap[key]=nod;
poz[nod]=key;
}
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
int i,n,j,p,m,a,b,c,nod;
scanf("%d%d",&n,&m);
for(i=1; i<=m; i++)
{
scanf("%d%d%d",&a,&b,&c);
v[a].push_back(make_pair(b,c));
}
for(i=1;i<=n;i++)
{
cost[i]=1987654321;
poz[i]=heap[i]=i;
}
cost[1]=0;
N=n;
for(j=1; j<=n; j++)
{int aux;
nod=heap[1];
heap[1]=heap[N];
heap[N]=nod;
poz[nod]=N;
poz[N]=1;
N--;
sift(1);
p=v[nod].size();
for(i=0;i<p;i++)
{
if(cost[v[nod][i].first]>cost[nod]+v[nod][i].second)
{
cost[v[nod][i].first]=cost[nod]+v[nod][i].second;
percolate(poz[v[nod][i].first]);
}
}
}
for(i=2;i<=n;i++)
{
if(cost[i]==1987654321)printf("0 ");
else printf("%d ", cost[i]);
}
return 0;
}