Cod sursa(job #340100)

Utilizator Data 13 august 2009 01:50:20 Algoritmul lui Dijkstra 100 cpp done Arhiva educationala 1.92 kb
``````#include <fstream>
#include <iostream>
#include <vector>
#define maxn 50010
#define inf 123456789

using namespace std;

int N,M, dist[maxn+100],poz[maxn+100], heap[maxn*5+100], hind, u,a ,b,c;
vector<pair<int,int> > vecini[maxn];
vector<pair<int,int> >::iterator it;
pair<int,int> temp;
inline void swap(int i, int j){
int z;

z=heap[i];
heap[i]=heap[j];
heap[j]=z;
poz[heap[i]]=i;
poz[heap[j]]=j;

}
inline void upheap(int);
inline void downheap(int);
inline void dellete(int i) {
swap(i,hind);
poz[heap[hind]]=-1;
//heap[hind]=0;
hind--;
downheap(i);
}
inline void upheap(int i) {
int x=0;
while (x!=i)
{
x=i;
if (dist[heap[i]]<dist[heap[i/2]]) i=i/2;
swap(x,i);
}
}
inline void downheap(int i) {
int x=0;
while (x!=i) {
x=i;
if (2*x<=hind&&dist[heap[i]]>dist[heap[2*x]]) i=2*x;
if (2*x+1<=hind&&dist[heap[i]]>dist[heap[2*x+1]]) i=2*x+1;
swap(i,x);
}
}
int main () {
ifstream in;
ofstream out;
in.open("dijkstra.in");
out.open("dijkstra.out");
in >> N >> M;
int i=0;
for (i=0; i<M; i++) {
in >> a >> b>>c;
temp.first=b;
temp.second=c;
vecini[a].push_back(temp);
}
dist[1]=0;
heap[1]=1;
poz[1]=1;
for (i=2; i<=N; i++)
{
dist[i]=inf;
heap[i]=i;
poz[i]=i;
}
hind=N;
int v,alt;
while (hind!=0) {
u=heap[1];
if (dist[u]==inf) break;
dellete(1);

for (it=vecini[u].begin();it!=vecini[u].end();it++) {
v=(*it).first;
alt=dist[u]+(*it).second;
if (alt<dist[v]) {
dist[v]=alt;
if (poz[v]>0) {
upheap(poz[v]);
}
}
}
}
for (i=2; i<=N; i++)
{
if (dist[i]==inf) out << 0 << " ";else out << dist[i] << " ";
}
out.close();
return 0;
}
``````