Pagini recente » Cod sursa (job #346079) | Cod sursa (job #2487089) | Cod sursa (job #1593852) | Cod sursa (job #1696803) | Cod sursa (job #161146)
Cod sursa(job #161146)
#include <stdio.h>
#include <vector>
#include <string.h>
#define maxl 50001
#define inf 1<<30
using namespace std;
vector <int> a[maxl];
vector <int> cost[maxl];
int heap[maxl],poz[maxl],dist[maxl];
int i,k,p,q,n,m,x,t;
char f[20];
int main()
{
freopen("dijkstra.in","r",stdin);
freopen("dijkstra.out","w",stdout);
scanf("%d %d\n",&n,&m);
for (i=1; i<=m; ++i)
{
fgets(f,18,stdin);
p=0;q=0;k=0;x=0;
while (f[x]!=' ') {p=p*10+f[x]-48;++x;}++x;
while (f[x]!=' ') {q=q*10+f[x]-48;++x;}++x;
while (f[x]!='\n') {k=k*10+f[x]-48;++x;}
a[p].push_back(q);
cost[p].push_back(k);
if (i<=n)
{
dist[i]=inf;heap[i]=i;poz[i]=i;
}
}
k=n;
dist[1]=0;
while (k>0)
{
p=a[heap[1]].size();
for (i=0; i<=p-1; ++i)
if (dist[heap[1]]+cost[heap[1]][i]<dist[a[heap[1]][i]])
{
dist[a[heap[1]][i]]=dist[heap[1]]+cost[heap[1]][i];
x=poz[a[heap[1]][i]];
while (x>>1>0)
{
if (dist[heap[x>>1]]>dist[heap[x]])
{
t=poz[heap[x]];poz[heap[x]]=poz[heap[x>>1]];poz[heap[x>>1]]=t;
t=heap[x>>1];heap[x>>1]=heap[x];heap[x]=t;
x>>=1;
}
else break;
}
}
//scoaterea elementului 1 din heap
poz[heap[1]]=k;poz[heap[k]]=1;
heap[1]=heap[k];
heap[k]=0;
k--;
x=1;
while (x*2<=k)
{
p=2*x;q=p;
if (q+1<=k) q++;
if (dist[heap[x]]>dist[heap[p]] || dist[heap[x]]>dist[heap[q]])
{
if (dist[heap[p]]<=dist[heap[q]])
{
t=poz[heap[x]];poz[heap[x]]=poz[heap[p]];poz[heap[p]]=t;
t=heap[x];heap[x]=heap[p];heap[p]=t;
x=p;
}
else {
t=poz[heap[x]];poz[heap[x]]=poz[heap[q]];poz[heap[q]]=t;
t=heap[x];heap[x]=heap[q];heap[q]=t;
x=q;
}
}
else break;
}
}
for (i=2; i<=n; ++i)
printf("%d ",dist[i]==inf?0:dist[i]);
printf("\n");
return 0;
}