#include<iostream>
using namespace std;
#define INT_MAX 2147483647
class queueINT {
private:
int front;
int rear;
int* head;
int length;
public:
queueINT(int len);
~queueINT();
void push(int e);
int pop();
bool isEmpty();
int howLong();
};
queueINT::queueINT(int len)
{
if (len <= 1) {
cout << "in queueINT(int len), len is too small" << endl;
len = 100;
}
head = new int[len];
length = len;
front = 0, rear = 0;
}
queueINT::~queueINT()
{
if (head != nullptr) {
delete[] head;
}
}
void queueINT::push(int e)
{
if ((rear + 1) % length == front)
{
int* newhead = new int[length * 2];
for (int i = 0; i < length - 1; i++)
{
newhead[i] = head[(front + i) % length];
}
delete[]head;
head = newhead;
front = 0, rear = length - 1;
length *= 2;
}
head[(rear++) % length] = e;
}
int queueINT::pop()
{
if (front == rear) {
return INT_MAX;
}
return head[(front++) % length];
}
bool queueINT::isEmpty()
{
return front == rear;
}
int queueINT::howLong()
{
return (rear - front + length) % length;
}
class stackINT {
private:
int* base;
int* top;
int length;
public:
stackINT(int len);
~stackINT();
void push(int e);
int pop();
bool isEmpty();
};
stackINT::stackINT(int len)
{
length = len;
base = new int[len];
top = base;
}
stackINT::~stackINT()
{
top = nullptr;
if (base != nullptr) delete[]base;
}
void stackINT::push(int e)
{
if (top - base == length) {
int* newbase = new int[length * 2];
for (int i = 0; i < length; i++) {
newbase[i] = base[i];
}
delete []base;
base = newbase;
top = length + base;
length *= 2;
}
*(top++) = e;
}
int stackINT::pop()
{
if (isEmpty()) {
return INT_MAX;
}
top--;
return *top;
}
bool stackINT::isEmpty()
{
return top == base;
}
class Dijkstra
{
public:
Dijkstra();
~Dijkstra();
Dijkstra(int**& matrix, int sumOfNodes);
void showNodes();
void shortestWay(int start);
void showShortest(int start);
private:
typedef struct Way {
int* nextNum;
int* val;
int sumOfWays;
Way()
{
nextNum = nullptr, val = nullptr;
sumOfWays = 0;
}
Way(int n)
{
nextNum = new int[n];
val = new int[n];
sumOfWays = n;
for (int i = 0; i < n; i++) {
nextNum[i] = 0, val[i] = 0;
}
}
~Way()
{
if (nextNum != nullptr) delete[] nextNum;
if (val != nullptr) delete[]val;
}
void assign(int n, int next, int value)
{
if (n < 0 || n >= sumOfWays) {
cout << "in Dijkstra, struct Way, void assign, n is out of arrange;" << endl;
exit(0);
}
nextNum[n] = next, val[n] = value;
}
}Way;
typedef struct Node {
int num;
Way ways;
Node(int _num,int lenOfWays):ways(lenOfWays) {
num = _num;
}
}Node;
typedef struct Signs {
int* priorNum;
int* sumCost;
int startNum;
Signs()
{
startNum = 0;
priorNum = nullptr, sumCost = nullptr;
}
Signs(int start, int n)
{
startNum = start;
priorNum = new int[n+1];
sumCost = new int[n+1];
for (int i = 0; i <= n; i++) {
priorNum[i] = start;
sumCost[i] = INT_MAX;
}
sumCost[start] = 0;
}
~Signs()
{
if (priorNum != nullptr) delete[] priorNum;
if (sumCost != nullptr) delete[]sumCost;
}
}Signs;
Node** nodes;
Signs** signs;
int jie;
};
Dijkstra::Dijkstra()
{
nodes = nullptr;
signs = nullptr;
jie = 0;
}
Dijkstra::~Dijkstra()
{
if (nodes != nullptr) {
for (int i = 0; i < jie; i++) {
delete nodes[i];
}
delete nodes;
}
if (signs != nullptr) {
for (int i = 0; i < jie; i++) {
delete signs[i];
}
delete signs;
}
}
Dijkstra::Dijkstra(int**& matrix, int sumOfNodes)
{
jie = sumOfNodes;
nodes = new Node*[sumOfNodes];
signs = new Signs*[sumOfNodes];
int* temp = new int[sumOfNodes];
for (int i = 0; i < sumOfNodes; i++)
{
temp[i] = 0;
for (int j = 0; j < sumOfNodes; j++) {
if (matrix[i][j]) temp[i]++;
}
}
for (int i = 0; i < sumOfNodes; i++) {
nodes[i] = new Node(i + 1, temp[i]);
for (int j = 0, k = 0; j < sumOfNodes; j++) {
if (matrix[i][j]) nodes[i]->ways.assign(k++, j + 1, matrix[i][j]);
}
signs[i] = new Signs(i + 1, sumOfNodes);
}
}
void Dijkstra::showNodes()
{
for (int i = 0; i < jie; i++)
{
cout << nodes[i]->num << ' ';
for (int j = 0; j < nodes[i]->ways.sumOfWays; j++) {
cout << '<' << nodes[i]->ways.nextNum[j] << ", " << nodes[i]->ways.val[j] << '>' << ' ';
}
cout << endl;
}
}
void Dijkstra::shortestWay(int start)
{
queueINT q(jie);
int* isRepeat = new int[jie + 1];
for (int i = 0; i <= jie; i++)isRepeat[i] = 0;
int curNum = 0, nextNum = 0;
q.push(start);
isRepeat[start] = 1;
while (!q.isEmpty())
{
curNum = q.pop();
for (int i = 0; i < nodes[curNum-1]->ways.sumOfWays; i++) {
nextNum = nodes[curNum - 1]->ways.nextNum[i];
if (isRepeat[nextNum] == 0) {
q.push(nextNum);
isRepeat[nextNum] = 1;
}
if (nodes[curNum - 1]->ways.val[i] + signs[start - 1]->sumCost[curNum] < signs[start - 1]->sumCost[nextNum])
{
int a = nodes[curNum - 1]->ways.val[i];
int b = signs[start - 1]->sumCost[curNum];
int d = signs[start - 1]->sumCost[nextNum];
int c = signs[start - 1]->priorNum[nextNum];
signs[start - 1]->priorNum[nextNum] = curNum;
signs[start - 1]->sumCost[nextNum] = nodes[curNum - 1]->ways.val[i] + signs[start - 1]->sumCost[curNum];
}
}
}
}
void Dijkstra::showShortest(int start)
{
if (start < 1 || start > jie) {
cout << "In Dijkstra, void showShortest, start is out of range" << endl;
return;
}
for (int i = 0; i < jie; i++) {
if (signs[start]->sumCost[i] == INT_MAX) {
shortestWay(start);
i = jie;
}
}
for (int i = 1, curPoint = 0; i <= jie; i++) {
if (i != start) {
int k = 0, * temp = new int[jie];
curPoint = i;
do {
temp[k++] = curPoint;
curPoint = signs[start-1]->priorNum[curPoint];
} while (curPoint != start);
cout << start;
while (--k >= 0) {
cout << temp[k];
}
cout << " ";
cout << signs[start - 1]->sumCost[i];
cout << endl;
}
}
}
int main()
{
int** p;
int n = 6;
p = new int* [n];
for (int i = 0; i < n; i++)p[i] = new int[n];
for (int i = 0, temp = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> temp;
p[i][j] = temp;
}
}
Dijkstra dj(p, n);
dj.showNodes();
dj.showShortest(1);
for (int i = 0; i < n; i++)delete p[i];
delete p;
return 0;
}