Taksi#9608

Taksi (Həll təhlili)

Çəki verilmiş qrafda Deykstra alqoritmi ilə müəyyən edilir:

$A$ nöqtəsindən $B$ nöqtəsinə olan ən qısa məsafə $d i s t_{ab}$ dist_{ab};
$A$ nöqtəsindən $C$ nöqtəsinə olan ən qısa məsafə $d i s t_{a c}$ dist_{ac};
$B$ nöqtəsindən $C$ nöqtəsinə olan ən qısa məsafə $d i s t_{b c}$ dist_{bc};

Sergeyi götürmədən İvan $d i s t_{a c}$ dist_{ac} məsafəsini gedir.

Sergeyi götürərək isə $d i s t_{ab} + d i s t_{b c}$ dist_{ab} + dist_{bc} uzunluğunda yol gedir.

Problemin cavabı bərabərdir

(d i s t_{ab} + d i s t_{b c} - d i s t_{a c}) * d

(dist_{ab} + dist_{bc} - dist_{ac}) * d

Bu, Sergeyi götürməyin nəticəsində səfərin daha bahalı olduğu məbləğdir.

Misal

Yol qrafı aşağıdakı şəkildədir:

Ən qısa məsafələri hesablayırıq:

$A$ -dan $B$ -yə olan ən qısa yol $d i s t_{ab}$ dist_{ab} $5.5$ -ə bərabərdir;
$A$ -dan $C$ -yə olan ən qısa yol $d i s t_{a c}$ dist_{ac} $7.5$ -ə bərabərdir;
$B$ -dən $C$ -yə olan ən qısa yol $d i s t_{b c}$ dist_{bc} $8$ -ə bərabərdir;

İvanın Sergeyi götürmədən getdiyi məsafə: $d i s t_{a c} = 7.5$ dist_{ac} = 7.5.

Sergeyi götürməklə gedilən məsafə: $d i s t_{ab} + d i s t_{b c} = 5.5 + 8 = 13.5$ dist_{ab} + dist_{bc} = 5.5 + 8 = 13.5.

Beləliklə, problemin cavabı bərabərdir:

(d i s t_{ab} + d i s t_{b c} - d i s t_{a c}) * d = (5.5 + 8 - 7.5) * 4.25 = 6 * 4.25 = 25.5

(dist_{ab} + dist_{bc} - dist_{ac}) * d = (5.5 + 8 - 7.5) * 4.25 = 6 * 4.25 = 25.5

Alqoritmin reallaşdırılması

Qraf çəki verilmiş qonşuluq matrisi $g$ şəklində saxlanılır. Ən qısa məsafələri saxlamaq üçün $d i s t$ və məsafəsi artıq hesablanmış zirvələri saxlamaq üçün $u se d$ massivini elan edirik.

#define MAX 110
double g[MAX][MAX], dist[MAX];
int used[MAX];

Dijkstra funksiyası $s$ zirvəsindən $f$ zirvəsinə ən qısa yolun uzunluğunu qaytarır.

double Dijkstra(int s, int f)
{
  memset(used, 0, sizeof(used));
  for (i = 1; i <= n; i++) dist[i] = 1e18;
  dist[s] = 0;

  for (i = 1; i < n; i++)
  {
    double min = 1e18;
    int w = -1;
    for (j = 1; j <= n; j++)
      if (used[j] == 0 && dist[j] < min) { min = dist[j]; w = j; }

    if (min == 1e18) break;

    for (j = 1; j <= n; j++)
      if (used[j] == 0) dist[j] = minimum(dist[j], dist[w] + g[w][j]);

    used[w] = 1;
  }
  return dist[f];
}

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%d %d %d %d %lf", &n, &a, &b, &c, &d);
scanf("%d", &m);
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++) g[i][j] = 1e18;

for (i = 0; i < m; i++)
{
  scanf("%d %d %lf", &s, &f, &w);
  g[s][f] = g[f][s] = w;
}

C++

$d i s t_{ab}, d i s t_{b c}, d i s t_{a c}$ dist_{ab}, dist_{bc}, dist_{ac} dəyərlərini hesablayırıq.

double d1 = Dijkstra(a, b);
double d2 = Dijkstra(b, c);
double ds = Dijkstra(a, c);

Əgər bu dəyərlərdən hansısa biri sonsuzluğa bərabərdirsə, bu, müvafiq marşrutun mövcud olmadığı deməkdir — bu halda $- 1$ çıxış edirik.

if (d1 == 1e18 || d2 == 1e18 || ds == 1e18) printf("-1\n");

Əks halda $(d i s t_{ab} + d i s t_{b c} - d i s t_{a c}) * d$ (dist_{ab} + dist_{bc} - dist_{ac}) * d cavabını çıxış edirik.

else printf("%lf\n", (d1 + d2 - ds) * d);