Cod sursa(job #433384)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 3 aprilie 2010 17:29:20
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define mp make_pair
#define pb push_back
#define N 50100
#define ls(st) st << 1
#define F first 
#define S second 
#define INF 0x3f3f3f3f


vector < pair <int, int> > a[N];
int n, m, k, poz[N], h[N], d[N];

void citire(), dijkstra();

int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	citire();
	dijkstra();
int i;
	for (i = 2; i <= n; ++i)
		printf("%d ", (d[i] == INF ? 0 : d[i]));
	printf("\n");
	
	return 0;
}

void citire(){
int i, x, y, z;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= m; ++i){
		scanf("%d %d %d", &x, &y, &z);
		a[x].pb(mp(y,z));
	}
}

void upheap(int w){
int father;
	while (w > 1){
		father = w >> 1;
		if (d[h[w]] < d[h[father]]){
			swap(poz[h[w]], poz[h[father]]);
			swap(h[w], h[father]);
			w = father;	
		}
		else
			return;
	}
}

void downheap(int w){
int son;
	while (ls(w) <= k){
		son = ls(w);
		if (son+1 <= k)
			if (d[h[son]] > d[h[son+1]])
				++son;
		if (d[h[w]] > d[h[son]]){
			swap(poz[h[w]], poz[h[son]]);
			swap(h[w], h[son]);
			w = son;
		}
		else
			return;
	} 
}

void dijkstra(){
int i, min, nod2, cost2;
	for (i = 2; i <= n; ++i) poz[i] = -1, d[i] = INF;
	poz[1] = 1; h[1] = 1; k = 1;

	while (k){
		min = h[1];
		swap(h[1], h[k]); 
		poz[h[1]] = 1;
		--k;
		downheap(1);
		
		for (i = 0; i < a[min].size(); ++i){
			nod2 = a[min][i].F; cost2 = a[min][i].S;
			if (d[min] + cost2 < d[nod2]){
				d[nod2] = d[min] + cost2;
				if (poz[nod2] == -1){
					++k;
					poz[nod2] = k;
					h[k] = nod2;
					upheap(k);
				}
				else
					upheap(poz[nod2]);
			}
		}
	}
}