Cod sursa(job #144864)

Utilizator byndrsnAlina Ene byndrsn Data 28 februarie 2008 05:04:26
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
// Dijkstra with buckets

#include <iostream>
#include <fstream>
#include <list>
#include <vector>

#define INFI 0x3f3f3f3f

using namespace std;

int M, N, C;
vector< list<int> > buckets;
vector< vector<int> > adj, len;
vector<int> dist;
int pos, final;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

list<int> l;
vector<int> v;
int a, b, c;

void read_graph(void) {
	fin >> N >> M;

	adj.resize(N, v);
	v.resize(N, 0);
	len.resize(N, v);

	C = 0;

	for (int i = 0; i < M; ++ i) {
		fin >> a >> b >> c;
		-- a; -- b;

		adj[a].push_back(b);
		len[a][b] = c;

		if (c > C)
		   C = c;
	}

	buckets.resize(C + 1, l);
}

int next_bucket(void) {
	for (int i = 0; i < C + 1; ++ i) {
		int k = (pos + i) % (C + 1);

		if (!buckets[k].empty())
			return k;
	}

	return -1;
}

void relax_neighbours(int u) {
	int n = adj[u].size();

	// relax all of u's neighbours
	for (int i = 0; i < n; ++ i) {
		int v = adj[u][i];

		if (dist[v] <= dist[u] + len[u][v])
			continue;

		if (dist[v] != INFI) {
			// remove v from the old bucket
			int t = dist[v] % (C + 1);
			buckets[t].remove(v);
		}

		// add v to its new bucket
		dist[v] = dist[u] + len[u][v];
		int t = dist[v] % (C + 1);
		buckets[t].push_back(v);
	}
}

void dijkstra(void) {
	dist.resize(N, INFI);
	dist[0] = pos = 0;
	final = N - 1;

	buckets[0].push_back(0);

	while (final > 0) {
		int k = next_bucket();
		assert(k != -1);

		int n = buckets[k].size();
		for (int i = 0; i < n; ++ i) {
			int u = buckets[k].back();
			relax_neighbours(u);

			// u's distance becomes permanent
			buckets[k].pop_back();
			-- final;
		}
	}
}

int main(void) {
	read_graph();
	dijkstra();

	for (int i = 1; i < N; ++ i)
		fout << dist[i] << " ";
	fout << endl;

	return 0;
}