Cow Routing (Bronze)#11185

Cow Routing (Bronze) (Editorial)

Each route defines a directed sequence of cities. Since Bessie wants to use only one route, for each route it is sufficient to check:

does city $A$ appear before city $B$ ?

If this condition is satisfied, Bessie can use that route and pay its fixed cost. Among all suitable routes, we need to find the route with the minimum cost.

Example

In the example, there are $3$ routes:

$3 \to 2 \to 1$ 3 \to 2 \to 1;
$2 \to 1 \to 4 \to 3$ 2 \to 1 \to 4 \to 3;
$4 \to 1 \to 7 \to 8 \to 2$ 4 \to 1 \to 7 \to 8 \to 2;

Since $A = 1$ A = 1 and $B = 2$ B = 2, Bessie can use only the third route, because city $1$ appears before city $2$ on that route. The cost of this route is $8$ .

Algorithm implementation

Define the constant $I N F$ .

#define INF 1000000000

Read the input data.

scanf("%d %d %d", &a, &b, &n);

Initialize the variable $r es$ that will store the answer.

res = INF;

Iterate over the $n$ routes.

for (i = 0; i < n; i++)
{

Read the route cost $cos t$ and the number of cities $sz$ on this route.

  scanf("%d %d", &cost, &sz);

The variable $f l a g$ is set to $f a l se$ if city $А$ has not yet appeared on the current route.

  flag = false;

Read the cities on the current route one by one.

  for (j = 0; j < sz; j++)
  {
    scanf("%d", &city);

If city $А$ is encountered, set $f l a g$ to $t r u e$ .

    if (city == a) flag = true;

If city $B$ is encountered and city $A$ has already appeared earlier on the route $(f l a g = t r u e)$ (flag = true), then Bessie can use this route and pay its cost $cos t$ .

If there are several suitable routes, choose the one with the minimum cost.

    if (flag && city == b) res = min(res, cost);
  }
}

After processing all routes, print the answer.

if (res == INF)
  printf("-1\n");
else
  printf("%d\n", res);