#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
int parnt[] = { -1, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3 };
int level[13] = { 0 };
int getLevel(int cur)
{
if (level[cur] != -1)
return level[cur];
if (parnt[cur] == -1)
{
level[cur] = 1;
return 1;
}
level[cur] = getLevel(parnt[cur]) + 1;
return level[cur];
}
struct edge
{
int a, b, cost;
edge(int a = 0, int b = 0, int cost = 0) :a(a), b(b), cost(cost){};
};
edge arr[13];
struct node
{
int value;
node* next;
node(int vl):value(vl){};
};
class stack
{
node* head;
public:
stack()
{
head = 0;
}
int top()
{
if (head == 0)
return -999999999;
return head->value;
}
bool isEmpty()
{
return head == 0;
}
void push(int vl)
{
node* newElem = new node(vl);
newElem->next = head;
head = newElem;
}
void pop()
{
if (head == 0)
return;
node* tmp = head;
head = head->next;
delete tmp;
}
void deleteNodeByVal(int vl)
{
node* cNode = head;
while (cNode != 0)
{
if (cNode->value == vl)
{
node* tmp = cNode;
cNode = cNode->next;
delete tmp;
continue;
}
else
{
cNode = cNode->next;
}
}
}
};
class PuchkiDug
{
private:
int* heads;
int* links;
edge* edges_p;
int n;
int m;
public:
PuchkiDug(edge* allEdges, int n, int m) : n(n), m(m)
{
edges_p = allEdges;
heads = new int[n];
links = new int[m];
memset(heads, -1, sizeof(int) * n);
memset(links, -1, sizeof(int) * m);
for (int i = 0; i < m; ++i)
{
links[i] = heads[edges_p[i].a];
heads[edges_p[i].a] = i;
}
}
void printData()
{
for (int i = 0; i < n; ++i)
{
int cr = heads[i];
while (cr != -1)
{
cout << edges_p[cr].b << " ";
cr = links[cr];
}
cout << endl;
}
}
void getParentTree(int* outp, int start)
{
memset(outp, -1, sizeof(int)* n);
queue<int> que;
que.push(start);
outp[start] = -2;
while (!que.empty())
{
int cr = que.front();
que.pop();
int hd = heads[cr];
while (hd != -1)
{
int to = edges_p[hd].b;
if (outp[to] == -1)
{
outp[to] = cr;
que.push(to);
}
hd = links[hd];
}
}
}
void djicstra(int* distances, edge* edges, int vCount, int eCount, int start)
{
int maxEdge = 0;
for (int i = 0; i < eCount; ++i)
{
maxEdge = max(maxEdge, edges[i].cost);
}
stack* cherpack = new stack[maxEdge];
distances[start] = 0;
bool isWorking = true;
cherpack[0].push(start);
while (isWorking)
{
isWorking = false;
for (int i = 0; i < maxEdge; ++i)
{
if (cherpack[i].isEmpty())
continue;
int cVert = cherpack[i].top();
cherpack[i].pop();
int dist = distances[cVert];
int cEdge = heads[cVert];
while (cEdge != -1)
{
int nx = edges[cEdge].b;
int cost = edges[cEdge].cost;
if (distances[nx] > distances[cVert] + cost)
{
int cherp = distances[nx] % maxEdge;
distances[nx] = distances[cVert] + cost;
cherpack[cherp].deleteNodeByVal(nx);
cherp = distances[nx] % maxEdge;
cherpack[cherp].push(nx);
isWorking = true;
}
cEdge = links[cEdge];
}
}
}
}
};
int main()
{
memset(level, -1, sizeof(int) * 13);
arr[0] = edge(0, 1, 2);
arr[1] = edge(0, 2, 4);
arr[2] = edge(0, 3, 1);
arr[3] = edge(1, 4, 20);
arr[4] = edge(1, 5, 30);
arr[5] = edge(1, 6, 13);
arr[6] = edge(2, 7, 12);
arr[7] = edge(2, 8, 23);
arr[8] = edge(2, 9, 41);
arr[9] = edge(3, 10, 51);
arr[10] = edge(3, 11, 53);
arr[11] = edge(3, 12, 93);
arr[12] = edge(3, 0, 85);
PuchkiDug puch(arr, 13, 13);
int dstts[13] = {0};
for (int i = 0; i < 13; ++i)
dstts[i] = 999999999;
puch.djicstra(dstts, arr, 13, 13, 3);
for (int i = 0; i < 13; ++i)
{
cout << dstts[i] << " ";
}
}