Pagini recente » Cod sursa (job #1322501) | Cod sursa (job #1097825)
#include<fstream>
using namespace std;
typedef struct celula {
int nod,cost;
celula *next;
}*lista;
typedef struct { int nod, cost; } tip;
lista graf[50005],v;
tip heap[250000];
int i,n,drum[50005],x,y,c,hp,m;
bool viz[50005];
void baga(int nod, int cost) {
++hp;
heap[hp].nod=nod;
heap[hp].cost=cost;
int aux=hp;
while (aux>1&&heap[aux/2].cost>heap[aux].cost) {
swap(heap[aux/2],heap[aux]);
aux/=2;
}
}
void sterge() {
heap[1]=heap[hp];
--hp;
int aux=1;
while (2*aux<=hp) {
int ind=aux;
if (heap[2*aux].cost<heap[ind].cost) ind=2*aux;
if (2*aux+1<=hp&&heap[2*aux+1].cost<heap[ind].cost) ind=2*aux+1;
if (ind==aux) break;
else { swap(heap[ind],heap[aux]); aux=ind; }
}
}
int main(void) {
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
fin>>n>>m;
for (i=1; i<=m; ++i) {
fin>>x>>y>>c;
v=new celula; v->nod=x; v->cost=c; v->next=graf[y]; graf[y]=v;
v=new celula; v->nod=y; v->cost=c; v->next=graf[x]; graf[x]=v;
}
baga(1,1);
while (hp) {
int nodc=heap[1].nod;
drum[nodc]=heap[1].cost;
sterge();
if (viz[nodc]==0) {
viz[nodc]=1;
for (lista p=graf[nodc]; p; p=p->next)
if (drum[p->nod]==0||drum[p->nod]>drum[nodc]+p->cost) {
drum[p->nod]=drum[nodc]+p->cost;
baga(p->nod,drum[p->nod]);
}
}
}
for (i=2; i<=n; ++i) fout<<drum[i]-1<<" ";
return(0);
}