// 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