Таксі#9608

Таксі (Розбір)

У зваженому графі за допомогою алгоритму Дейкстри визначаються:

найкоротша відстань $d i s t_{ab}$ dist_{ab} від пункту $A$ до пункту $B$ ;
найкоротша відстань $d i s t_{a c}$ dist_{ac} від пункту $A$ до пункту $C$ ;
найкоротша відстань $d i s t_{b c}$ dist_{bc} від пункту $B$ до пункту $C$ ;

Без заїзду за Сергієм Іван проїжджає відстань $d i s t_{a c}$ dist_{ac}.

З заїздом за Сергієм він проїжджає шлях довжиною $d i s t_{ab} + d i s t_{b c}$ dist_{ab} + dist_{bc}.

Відповідь на задачу дорівнює

(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

Це сума, на яку поїздка стала дорожчою через заїзд за Сергієм.

Приклад

Граф доріг має такий вигляд:

Визначимо найкоротші відстані:

найкоротший шлях $d i s t_{ab}$ dist_{ab} від $A$ до $B$ дорівнює $5.5$ ;
найкоротший шлях $d i s t_{a c}$ dist_{ac} від $A$ до $C$ дорівнює $7.5$ ;
найкоротший шлях $d i s t_{b c}$ dist_{bc} від $B$ до $C$ дорівнює $8$ ;

Відстань, яку проїжджає Іван без заїзду за Сергієм: $d i s t_{a c} = 7.5$ dist_{ac} = 7.5.

Відстань з заїздом за Сергієм: $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.

Тоді відповідь на задачу дорівнює:

(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

Реалізація алгоритму

Граф зберігаємо у вигляді зваженої матриці суміжності $g$ . Оголосимо масив найкоротших відстаней $d i s t$ і масив $u se d$ , що містить інформацію про вершини, для яких відстань вже обчислена.

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

Функція Dijkstra повертає довжину найкоротшого шляху від вершини $s$ до вершини $f$ .

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

Основна частина програми. Зчитуємо вхідні дані.

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}.

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

Якщо хоча б одне з цих значень дорівнює нескінченності, це означає, що відповідного маршруту не існує — в цьому випадку виводимо $- 1$ .

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

Інакше виводимо відповідь $(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.

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