Taxi#9608

Taxi (Editorial)

In a weighted graph, Dijkstra's algorithm is used to determine:

the shortest distance $d i s t_{ab}$ dist_{ab} from point $A$ to point $B$ ;
the shortest distance $d i s t_{a c}$ dist_{ac} from point $A$ to point $C$ ;
the shortest distance $d i s t_{b c}$ dist_{bc} from point $B$ to point $C$ ;

Without picking up Sergey, Ivan travels a distance of $d i s t_{a c}$ dist_{ac}.

With a detour to pick up Sergey, the total distance becomes $d i s t_{ab} + d i s t_{b c}$ dist_{ab} + dist_{bc}.

The answer to the problem is:

(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

This is the additional amount the trip costs due to picking up Sergey.

Example

The road graph is as follows:

Let’s compute the shortest distances:

the shortest path $d i s t_{ab}$ dist_{ab} from $A$ to $B$ is $5.5$ ;
the shortest path $d i s t_{a c}$ dist_{ac} from $A$ to $C$ is $7.5$ ;
the shortest path $d i s t_{b c}$ dist_{bc} from $B$ to $C$ is $8$ ;

The distance Ivan travels without picking up Sergey: $d i s t_{a c} = 7.5$ dist_{ac} = 7.5.

The distance with a detour to pick up Sergey: $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.

Thus, the answer to the problem is:

(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

Algorithm implementation

The graph is stored as a weighted adjacency matrix $g$ . Declare an array of shortest distances $d i s t$ and an array $u se d$ , which holds information about the vertices for which the shortest distance is calculated.

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

The Dijkstra function returns the length of the shortest path from vertex $s$ to vertex $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++

The main part of the program. Read the input data.

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

Compute the values of $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);

If at least one of these values is equal to infinity, it means that the corresponding route does not exist — in this case print $- 1$ .

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

Otherwise, print the result: $(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);