#include <iostream>
#include <queue>
#include <cstdio>
#include <string>
#include <cmath>
#define forn(i, n, k) for(int i = k; i < n; ++i)
using namespace std;
struct edge { // ребрышки:)
int a, // beginning of arc
b, // end of arc
cost; // cost of arc
edge(int a = 0, int b = 0, int cost = 0): a(a), b(b), cost(cost) {};
};
class cherpack {
public:
int* heads;
int* backLinks;
int* forwardLinks;
int n,
m;
public:
cherpack(int n, int m): n(n), m(m) {
heads = new int[m];
backLinks = new int[n];
forwardLinks = new int[n];
forn(i, m, 0)
heads[i] = -1;
//memset(heads, -1, sizeof(int) * m);
}
int get(int k) {
int head = heads[k];
if (head != -1)
heads[k] = forwardLinks[head];
return head;
}
void insert(int vert, int k) {
int head = heads[k];
forwardLinks[vert] = head;
if (head != -1)
backLinks[head] = vert;
heads[k] = vert;
}
void remove(int vert, int k) {
int forwardd = forwardLinks[vert],
back = backLinks[vert];
if (vert == heads[k])
heads[k] = forwardd;
else {
forwardLinks[back] = forwardd;
if (forwardd != -1)
backLinks[forwardd] = back;
}
}
};
class pd { // пучечки дужег:)
private:
int* heads; // heads of lists
int* links; // links of items
edge* p_edges; // edges/arcs
int n, // number of vertices
m; // number of edges/arcs
public:
pd(edge* edges, int n, int m): n(n), m(m) {
p_edges = edges;
heads = new int[n];
links = new int[m];
//memset(heads, -1, sizeof(int) * n);
//memset(links, -1, sizeof(int) * m);
forn(i, n, 0)
heads[i] = -1;
forn(i, m, 0)
links[i] = -1;
forn(i, m, 0) {
links[i] = heads[p_edges[i].a];
heads[p_edges[i].a] = i;
}
}
void print() {
cout << "puchki dug:" << endl;
forn(i, n, 0) {
int curVert = heads[i];
string list = "";
bool isAlone = true;
for (int k = curVert; k != - 1; k = links[k]) {
int nextVert = p_edges[k].b;
list += to_string(nextVert) + " ";
isAlone = false;
}
if (!isAlone)
cout << i << ": " << list << endl;
}
}
int* getParentTree(int vert) {
int* retValue = new int[n];
forn(i, n, 0)
retValue[i] = -1;
//memset(retValue, -1, sizeof(int) * n);
queue<int> q;
q.push(vert);
retValue[vert] = -2;
while(!q.empty()) {
int from = q.front();
q.pop();
int curVert = heads[from];
for (int k = curVert; k != - 1; k = links[k]) {
int nextVert = p_edges[k].b;
if (retValue[nextVert] == -1) {
retValue[nextVert] = from;
q.push(nextVert);
}
}
}
return retValue;
}
int* getDestTree(int vert) {
int C = 0; // max cost holacoste:)
forn(i, m, 0)
C = max(C, p_edges[i].cost);
int INF = C + 1;
int* dest = new int[n]; // retValue
int* parent = new int[n];
forn(i, n, 0) {
dest[i] = INF;
parent[i] = -2;
}
//memset(dest, INF, sizeof(int) * n);
//memset(parent, -2, sizeof(int) * n);
dest[vert] = 0;
parent[vert] = -1;
int M = n * C; // max size of cherpack tupac:)
cherpack bucket(n, M);
bucket.insert(vert, 0);
forn(b, M, 0) {
int i = 0;
while((i = bucket.get(b)) != -1) { // смотрим дуги, выходящие из i
for (int k = heads[i]; k != -1; k = links[k]) {
int to = p_edges[k].b; // противоположная вершина
int destTo = dest[to];
if (dest[i] + p_edges[k].cost < destTo) { // проверка основного положения
dest[to] = dest[i] + p_edges[k].cost;
parent[to] = k;
if (destTo < INF) // если противоложная вершина помечана, то удаляем ее из черпака
bucket.remove(to, destTo);
bucket.insert(to, dest[to]);
}
}
}
}
forn(i, n, 0)
if (dest[i] > M)
dest[i] = -1;
return dest;
}
};
int n = 9,
m = 9;
edge* edges;
int main() {
edges = new edge[n];
edges[0] = edge(0, 1, 1);
edges[1] = edge(0, 2, 2);
edges[2] = edge(0, 3, 3);
edges[3] = edge(1, 4, 4);
edges[4] = edge(1, 5, 5);
edges[5] = edge(1, 6, 4);
edges[6] = edge(2, 7, 3);
edges[7] = edge(2, 8, 2);
edges[8] = edge(3, 0, 15);
pd puchock(edges, n, m);
puchock.print();
int* parent = puchock.getParentTree(3);
forn(i, n, 0)
cout << parent[i] << " ";
cout << endl;
int* dest = puchock.getDestTree(3);
forn(i, n, 0)
cout << dest[i] << " ";
return 0;
}