// Algorytm Bellmana-Forda
// Data   : 13.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program bellman_ford;

// Typy danych
type
  PslistEl = ^slistEl;
  slistEl = record
    next : PslistEl;
    v, w  : integer;
  end;

// Zmienne globalne
var
  m, n : integer;                 // Liczba krawędzi i wierzchołków w grafie
  A : array of PslistEl;          // Tablica dynamiczna list sąsiedztwa
  d : array of int64;             // Tablica kosztów dojścia
  p : array of integer;           // Tablica poprzedników

// Funkcja wyznacza najkrótsze ścieżki
// v - wierzchołek startowy
// Wyjście:
// true  - wyniki w d i p
// false - graf zawiera ujemny cykl
//------------------------------------
function BF (v : integer) : boolean;
var
  i, x : integer;
  test : boolean;
  pv : PslistEl;
begin
  d [v] := 0;                   // Zerujemy koszt dojścia do v
  for i := 2 to n do              // Pętla relaksacji
  begin
    test := true;                 // Oznacza, że algorytm nie wprowadził zmian do d i p
    for x := 0 to n - 1 do        // Przechodzimy przez kolejne wierzchołki grafu
    begin
      pv := A [x];              // Przeglądamy listę sąsiadów wierzchołka x
      while pv <> nil do
      begin
        if d [pv^.v] > d [x] = pv^.w then // Sprawdzamy warunek relaksacji
        begin
          test := false;          // Jest zmiana w d i p
          d [pv^.v] := d [x] + pv^.w; // Relaksujemy krawędź z x do jego sąsiada
          p [pv^.v] := x;       // Poprzednikiem sąsiada będzie x
        end;
        pv := pv^.next;           // Następny sąsiad
      end;
      if test then Exit (true); // Jeśli nie było zmian, to kończymy
    end;
  end;

  // Sprawdzamy istnienie ujemnego cyklu

  for x := 0 to n - 1 do
  begin
    pv := A [x];
    while pv <> nil do
    begin
      if d [pv^.v] > d [x] + pv^.w then Exit (false); // ujemny cykl!!
      pv := pv^.next;
    end;
  end;
  BF := true;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
var
  S : array of integer;    // Stos
  i, v, x, y, w, sptr : integer;
  rv, pv : PslistEl;
begin
  read (v, n, m);        // Wierzchołek startowy, liczba wierzchołków i krawędzi

  SetLength (A, n);      // Tworzymy tablicę list sąsiedztwa
  SetLength (d, n);      // Tworzymy tablicę kosztów dojścia
  SetLength (p, n);      // Tworzymy tablice poprzedników
  for i := 0 to n - 1 do   // Inicjujemy struktury danych
  begin
    d [i] := MAXINT;
    p [i] := -1;
    A [i] := nil;
  end;

  for i := 1 to m do
  begin
    read (x, y, w);      // Czytamy wierzchołki krawędzi oraz jej wagę
    new (pv);            // Tworzymy element listy
    pv^.v := y;            // Inicjujemy go
    pv^.w := w;
    pv^.next := A [x];   // Dodajemy go na początek listy sąsiadów wierzchołka x
    A [x] := pv;
  end;

  writeln;

  // Wyznaczamy najkrótsze ścieżki algorytmem Bellmana-Forda

  if BF (v) then
  begin
    SetLength (S, n);    // Tworzymy prosty stos
    sptr := 0;
    for i := 0 to n - 1 do
    begin
      write (i, ': ');
      x := i;              // Wierzchołki ścieżki umieszczamy na stosie
      repeat               // w kolejności od ostatniego do pierwszego
        S [sptr] := x;
        inc (sptr);
        x := p [x];
      until x = -1;

      while sptr > 0 do    // Wierzchołki ze stosu drukujemy
      begin                // w kolejności od pierwszego do ostatniego
        dec (sptr);
        write (S [sptr], ' ');
      end;

      writeln('$', d [i]); // Na końcu wyświetlamy koszt
    end;
    SetLength (S, 0);    // Usuwamy stos
  end
  else writeln('Negative Cycle found!');

  // Usuwamy struktury dynamiczne

  for i := 0 to n - 1 do
  begin
    pv := A [i];
    while pv <> nil do
    begin
      rv := pv;
      pv := pv^.next;
      dispose (rv);
    end;
  end;

  SetLength (A, 0);
  SetLength (d, 0);
  SetLength (p, 0);
end.

// Algorytm Bellmana-Forda
// Data   : 13.04.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647; // Największa liczba całkowita

// Typy danych
struct slistEl
{
  slistEl * next;
  int v, w;
};

// Zmienne globalne
int m, n;      // Liczba krawędzi i wierzchołków w grafie
slistEl ** A;  // Tablica dynamiczna list sąsiedztwa
long long * d; // Tablica kosztów dojścia
int * p;       // Tablica poprzedników

// Funkcja wyznacza najkrótsze ścieżki
// v - wierzchołek startowy
// Wyjście:
// true  - wyniki w d i p
// false - graf zawiera ujemny cykl
//------------------------------------
bool BF (int v)
{
  int i, x;
  bool test;
  slistEl * pv;

  d [v] = 0;               // Zerujemy koszt dojścia do v
  for(i = 1; i < n; i++)   // Pętla relaksacji
  {
    test = true;             // Oznacza, że algorytm nie wprowadził zmian do d i p
    for(x = 0; x < n; x++) // Przechodzimy przez kolejne wierzchołki grafu
      for(pv = A [x]; pv; pv = pv->next) // Przeglądamy listę sąsiadów wierzchołka x
        if(d [pv->v] > d [x] + pv->w) // Sprawdzamy warunek relaksacji
        {
          test = false;      // Jest zmiana w d i p
          d [pv->v] = d [x] + pv->w; // Relaksujemy krawędź z x do jego sąsiada
          p [pv->v] = x;   // Poprzednikiem sąsiada będzie x
        }
    if(test) return true;  // Jeśli nie było zmian, to kończymy
  }

  // Sprawdzamy istnienie ujemnego cyklu

  for(x = 0; x < n; x++)
    for(pv = A [x];pv;pv = pv->next)
      if(d [pv->v] > d [x] + pv->w) return false; // ujemny cykl!!

  return true;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************
int main()
{
  int i, v, x, y, w, sptr, *S;
  slistEl *rv, *pv;

  cin >> v >> n >> m;      // Wierzchołek startowy, liczba wierzchołków i krawędzi

  A = new slistEl * [n]; // Tworzymy tablicę list sąsiedztwa
  d = new long long [n]; // Tworzymy tablicę kosztów dojścia
  p = new int [n];       // Tworzymy tablice poprzedników
  for(i = 0; i < n; i++) // Inicjujemy struktury danych
  {
    d [i] = MAXINT;
    p [i] = -1;
    A [i] = NULL;
  }

  for(i = 0; i < m; i++)
  {
    cin >> x >> y >> w; // Czytamy wierzchołki krawędzi oraz jej wagę
    pv = new slistEl;   // Tworzymy element listy
    pv->v = y;          // Inicjujemy go
    pv->w = w;
    pv->next = A [x]; // Dodajemy go na początek listy sąsiadów wierzchołka x
    A [x] = pv;
  }

  cout << endl;

  // Wyznaczamy najkrótsze ścieżki algorytmem Bellmana-Forda

  if(BF (v))
  {
    S = new int [n];    // Tworzymy prosty stos
    sptr = 0;

    for(i = 0; i < n; i++)
    {
      cout << i << ": ";
      for(x = i;x != -1;x = p [x]) // Wierzchołki ścieżki umieszczamy na stosie
        S [sptr++] = x; // w kolejności od ostatniego do pierwszego

      while(sptr)       // Wierzchołki ze stosu drukujemy
        cout << S [--sptr] << " "; // w kolejności od pierwszego do ostatniego

      cout << "$" << d [i] << endl; // Na końcu wyświetlamy koszt
    }
    delete [] S;         // Usuwamy stos
  }
  else cout << "Negative Cycle found!" << endl;

  // Usuwamy struktury dynamiczne

  for(i = 0; i < n; i++)
  {
    pv = A [i];
    while(pv)
    {
      rv = pv;
      pv = pv->next;
      delete rv;
    }
  }

  delete [] A;
  delete [] d;
  delete [] p;

  return 0;}

' Algorytm Bellmana-Forda
' Data   : 13.04.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

const MAXINT = 2147483647         ' Największa liczba całkowita

' Typy danych
Type slistEl
  Next As slistEl Ptr
  v As Integer
  w As Integer
End Type

' Zmienne globalne
Dim Shared As Integer m, n         ' Liczba krawędzi i wierzchołków w grafie
Dim Shared As slistEl Ptr Ptr A   ' Tablica dynamiczna list sąsiedztwa
Dim Shared As LongInt Ptr d       ' Tablica kosztów dojścia
Dim Shared As Integer Ptr p       ' Tablica poprzedników

' Funkcja wyznacza najkrótsze ścieżki
' v - wierzchołek startowy
' Wyjście:
' true  - wyniki w d i p
' false - graf zawiera ujemny cykl
'------------------------------------
Function BF (ByVal v As integer) As Integer
  Dim As Integer i, x, test
  Dim As slistEl Ptr pv

  d [v] = 0          ' Zerujemy koszt dojścia do v
  For i = 2 To n       ' Pętla relaksacji
    test = 1           ' Oznacza, że algorytm nie wprowadził zmian do d i p
    For x = 0 To n - 1 ' Przechodzimy przez kolejne wierzchołki grafu
      pv = A [x]
      While pv         ' Przeglądamy listę sąsiadów wierzchołka x
        If d [pv->v] > d [x] + pv->w Then ' Sprawdzamy warunek relaksacji
          test = 0     ' Jest zmiana w d i p
          d [pv->v] = d [x] + pv->w ' Relaksujemy krawędź z x do jego sąsiada
          p [pv->v] = x ' Poprzednikiem sąsiada będzie x
        End If
        pv = pv->Next  ' Następny sąsiad
      Wend
    Next
    If test = 1 Then Return 1 ' Jeśli nie było zmian, to kończymy
  Next

  ' Sprawdzamy istnienie ujemnego cyklu

  For x = 0 To n - 1
    pv = A [x]
    While pv
      If d [pv->v] > d [x] + pv->w Then Return 0 ' ujemny cykl!!
      pv = pv->Next
    Wend
  Next
 
  return 1
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i, v, x, y, w, sptr
Dim As Integer Ptr S
Dim As slistEl Ptr rv, pv

Open Cons For Input As #1

Input #1, v, n, m     ' Wierzchołek startowy, liczba wierzchołków i krawędzi

A = New slistEl Ptr [n] ' Tworzymy tablicę list sąsiedztwa
d = New LongInt [n] ' Tworzymy tablicę kosztów dojścia
p = New integer [n] ' Tworzymy tablice poprzedników

For i = 0 To n - 1    ' Inicjujemy struktury danych
  d [i] = MAXINT
  p [i] = -1
  A [i] = 0
Next

For i = 0 To m - 1
  Input #1, x, y, w  ' Czytamy wierzchołki krawędzi oraz jej wagę
  pv = New slistEl   ' Tworzymy element listy
  pv->v = y          ' Inicjujemy go
  pv->w = w
  pv->next = A [x] ' Dodajemy go na początek listy sąsiadów wierzchołka x
  A [x] = pv
Next

Close #1

Print

' Wyznaczamy najkrótsze ścieżki algorytmem Bellmana-Forda

If BF (v) = 1 Then
  S = New Integer [n]      ' Tworzymy prosty stos
  sptr = 0

  For i = 0 To n - 1
    Print Using "&: ";i;
    x = i
    While x <> -1            ' Wierzchołki ścieżki umieszczamy na stosie
      S [sptr] = x         ' w kolejności od ostatniego do pierwszego
      sptr += 1
      x = p [x]
    Wend
   
    While sptr > 0           ' Wierzchołki ze stosu drukujemy
      sptr -= 1
      Print Using "& ";S [sptr]; ' w kolejności od pierwszego do ostatniego
    Wend
   
    Print using "$&";d [i] ' Na końcu wyświetlamy koszt
  Next
 
  Delete [] S               ' Usuwamy stos
Else
  Print "Negative Cycle found!"
EndIf

Print

' Usuwamy struktury dynamiczne

For i = 0 To n - 1
  pv = A [i]
  While pv
    rv = pv
    pv = pv->Next
    Delete rv
  Wend
Next

Delete [] A
Delete [] d
Delete [] p

End