Pagini recente » Cod sursa (job #519731) | Cod sursa (job #1793429) | Cod sursa (job #2811896) | Cod sursa (job #942667) | Cod sursa (job #1163448)
#include <cstdio>
#include <vector>
#include <utility>
#define N 50005
using namespace std;
vector< pair< int, int> > v[N];
int n,m,i,d[N],h[N],p[N],L,a,b,c,oo=50000010,nod,cost;
void sw(int,int),HU(int),HD(int);
int main()
{
freopen("dijstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d%d",&n,&m);
for(;m;m--)
{
scanf("%d%d%d",&a,&b,&c);
v[a].push_back(make_pair(b,c));
}
for(i=1;i<=n;i++){d[i]=oo;h[i]=p[i]=i;}
d[1]=0;L=n;
for(;L&&d[h[1]]!=oo;)
{
nod=h[1];cost=d[nod];
sw(1,L);L--;HD(1);
for(vector<pair<int,int> > ::iterator it=v[nod].begin();it!=v[nod].end();it++)
if(p[it->first]<=L)
if(d[it->first]>cost+it->second)
{
d[it->first]=cost+it->second;
HU(p[it->first]);
}
}
for(i=2;i<=n;i++)
d[i]==oo?printf("0 "):printf("%d ",d[i]);
return 0;
}
void sw(int i,int j)
{
int aux=h[i];h[i]=h[j];h[j]=aux;
p[h[i]]=i;p[h[j]]=j;
}
void HU(int fiu)
{
int tata=fiu>>1;
if(!tata)return;
if(d[h[fiu]]<d[h[tata]]){sw(tata,fiu);HU(tata);}
}
void HD(int tata)
{
int fiu=tata<<1;
if(fiu>L)return;
if(fiu<L&&d[h[fiu]]>d[h[fiu+1]])fiu++;
if(d[h[fiu]]<d[h[tata]]){sw(tata,fiu);HD(fiu);}
}