INFOMAN брой 18

/*
 Задача 5. Билети (давана и на ЗМС'97 8-9 клас)
 Условие:
 Даден е път между точките 1 и N (минаващ през 2, 3, ..., N-1 в този ред)
 разстоянието между всеки две от тях има определена цена и може да бъде
 изминавано само от по-малката към по-голямата. Да се намери такава серия от
 прехвърляния, че да може да се измине разстоянието от 1 до N за минимална
 цена.

 Решение:
 Ще използваме метода на динамичното оптимиране. Таблицата ни ще бъде
 dist[i][j], (където i е началната, а j крайната точки.) Рекурентната връзка
 ще е:
 dist[1][j] = min( dist[1][k] + dist[k][j] ), за k = 2, ..., j - 1
 За да намерим обратния път, за всяка точка j, ще помним във from[j] от коя
 друга точка k сме дошли, и тъй като възможността е само една за всяка точка,
 това ще ни гарантира запомнянето на обратния път. За да възстановим самия
 обратен път, ще е нужно само да обходим таблицата отзад напред. За съжаление
 по този начин намираме пътя в обратен ред и само за обръщането му са ни
 нужни стека path и указателя pp.
 Числата с които работим са цели, защото всяко число с фиксирана запетая може
 да се представи като цяло, а компютърът извършва по-бързо и по-коректно
 целочислени операции. Самото представяне на числа с 2 символа след запетаята
 става така: F * 100 = I където F е число с фиксирана запетая, а I цяло число.
*/

#include <stdio.h>

#define MAX 100

double dist[5][5] = {{ 0, 0, 0, 0,  0 },
                     { 0, 0, 3, 9, 20 },
                     { 0, 0, 0, 7, 16 },
                     { 0, 0, 0, 0, 10 },
                     { 0, 0, 0, 0,  0 }};
int from[MAX];
int path[MAX], pp;

int n = 4;

main()
{
  int i, j;
  double v;

  for( i = 1; i <= n; from[i++] = 1 );

  for( i = 3; i <= n; i++ )
    for( j = 2; j < i; j++ )
      if( dist[1][i] > ( v = dist[1][j] + dist[j][i] ))
        dist[1][i] = v, from[i] = j;

  for( path[0] = n, pp = 1, i = n; i != 1;)
    path[pp++] = i = from[i];

  printf( "%d", --pp );
  for( i = pp; i; i-- )
    printf( "\n%d %d", path[i], path[i - 1] );
}