#include <iostream.h>
#include <conio.h>

const int n=7;
int beg,end;
int G[n][n];
int R[n][n];
char key;

void GUnit()
{
for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
        G[i][j]=10000;
}

void initR()
{
for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
        R[i][j]=0;
}


void zeruj(int g[n][n])
{
for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
        g[i][j]=0;
}

void floyd(int g[n][n])
{
for(int k=0;k<n;k++)
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if( g[i][k]+g[k][j]<g[i][j])
        {
         g[i][j]=g[i][k]+g[k][j];
         R[i][j]=k;
        }
}

void droga(int i, int j)
{
int k = R[i][j];
if (k != 0)
 {
  droga(i,k);
  cout << k << " --> ";
  droga(k,j);
  }
}



int main()
{

do {
GUnit();
initR();

G[0][3]=30; G[0][1]=10;
G[1][2]=15; G[1][4]=40;
G[2][3]=5;  G[2][4]=20;
G[4][5]=20; G[4][6]=10;
G[5][6]=5;
G[6][3]=25;


cout << "\n\nPodaj wierzcholek poczatkowy: ";
cin >> beg;
cout << "Podaj wierzcholek koncowy: ";
cin >> end;

     if(G[beg][end]==10000) {
        cout << "\n\nNiestety, ale nie ma drogi bezposrednio z wierzcholka " << beg <<" do "<< end <<".";
     } else {
        cout <<"\n\nNajkrotsza droga wg przebytych krawedzi, waga wynosi "<<G[beg][end]<<" przebiega nastepujaco:\n";
        cout << beg <<" --> ";
        droga(beg,end);
        cout << end;
     }
        floyd(G);
        if(G[beg][end]==10000) {
        cout << "\n\nNiestety, ale tutaj tez nie ma bezposredniego polaczenia. ";
        } else {
        cout <<"\n\nNajkrotsza droga wg wagi, gdzie wynosi ona "<<G[beg][end]<<" przebiega nastepujaco:\n";
        cout << beg <<" --> ";
        droga(beg,end);
        cout << end;
        }
key = getch();
} while(key!='q');
}