Cod sursa(job #936794)
#include <vector>
#include <fstream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef pair<int, int> pr;
const int NMAX = 50011;
const int oo = 1 << 29;
int lHeap;
vector<pr> G[NMAX];
vector<pr>::iterator it, iend;
int d[NMAX], H[NMAX], P[NMAX];
inline void swap(int& x, int& y) {int aux = x; x = y; y = aux;}
void DownHeap(int k)
{
for(int son = k << 1; son <= lHeap; k = son, son <<= 1)
{
if(son < lHeap && d[H[son + 1]] < d[H[son]])
++son;
if(d[H[k]] <= d[H[son]]) return;
swap(H[k], H[son]);
P[H[son]] = son;
P[H[k]] = k;
}
}
void UpHeap(int k)
{
for(int f = k >> 1, key = d[H[k]]; k > 1 && key < d[H[f]]; k = f, f >>= 1)
{
swap(H[k], H[f]);
H[P[k]] = k;
H[P[f]] = f;
}
}
inline void push(int x)
{
H[++lHeap] = x;
P[x] = lHeap;
UpHeap(lHeap);
}
inline int pop()
{
int ans = H[1];
P[H[1]] = -1;
H[1] = H[lHeap--];
if(lHeap) P[H[1]] = 1;
DownHeap(1);
return ans;
}
int main()
{
int N, M, x, y, c;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
for(in >> N >> M; M; --M)
{
in >> x >> y >> c;
G[x].push_back(pr(y, c));
}
d[1] = 0;
for(push(1); lHeap; )
{
x = pop();
for(it = G[x].begin(), iend = G[x].end(); it < iend; ++it)
{
if(-1 == P[it->first]) continue;
if(!P[it->first])
{
d[it->first] = d[x] + it->second;
push(it->first);
}
else if(d[it->first] > d[x] + it->second)
{
d[it->first] = d[x] + it->second;
UpHeap(P[it->first]);
}
}
}
copy(d + 2, d + N + 1, ostream_iterator<int>(out, " "));
out << '\n';
return EXIT_SUCCESS;
}