include iostream include queue include cstdio include string include c

#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;
}