Pagini recente » Cod sursa (job #1886549) | Cod sursa (job #2596925) | Cod sursa (job #184013) | Cod sursa (job #941468) | Cod sursa (job #144864)
Cod sursa(job #144864)
// 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;
}