Metro (Editorial)

The shortest distance from the source to a vertex $v$ belonging to line $l$ is stored in dist[v][l], where 1 \le v \le 70 and 1 \le l \le 10. The graph is represented as an adjacency list. For each edge, in addition to its direction and cost, the number of the metro line to which the destination vertex belongs is also stored.

The algorithm starts from station $s$, located on line $line1$. The goal is to find the minimum travel cost required to reach station $f$, which lies on line $line2$.

When moving between vertices, it is necessary to check whether they belong to the same line: if the lines differ, an additional cost of $1$ is added (representing a line transfer).

Using Dijkstra's algorithm, we find the shortest distance from state (s, line1) to state (f, line2).

Example

In the given example, it is required to find the shortest route from station $2$ on line $1$ to station $7$ on line $3$.

• Move along line $1$ from station $2$ to station $1$: $2$ minutes.

• Transfer at station $1$ from line $1$ to line $2$: $1$ minute.

• Move along line $2$ from station $1$ to station $5$: $4$ minutes.

• Transfer at station $5$ from line $2$ to line $3$: $1$ minute.

• Move along line $3$ from station $5$ to station $7$: $2$ minutes.

Thus, the entire trip takes $10$ minutes.

Algorithm implementation

The number of vertices in the graph does not exceed MAX = 71. The number of metro lines does not exceed LINES = 11.

#define MAX 71
#define LINES 11

The shortest distance from the source to a vertex $v$ belonging to line $l$ is stored in dist[v][l]. We declare an array to store the shortest distances.

int dist[MAX][LINES];

The structure node contains information about an edge:

• $to$ is the destination vertex;

• $cost$ is the cost of the edge;

• $line$ is the metro line to which the edge belongs;

struct node
{
  int to, cost, line;
  node(int to, int cost, int line) : to(to), cost(cost), line(line) {}
};

The node structure is also used in the priority queue, where:

• $to$ is the current vertex;

• $cost$ is the minimum travel cost to reach vertex $to$ (on line $line$);

• $line$ is the metro line number on which vertex $to$ is located.

In the priority queue, vertices are ordered by increasing travel cost.

bool operator< (node a, node b)
{
  return a.cost > b.cost;
}

Declare an adjacency list to represent the graph.

vector<vector<node> > g;

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

scanf("%d %d", &n, &l);
g.resize(n + 1);

Read the $i$-th metro line. The travel time between two consecutive stations $u$ and $v$ is $2$.

for (i = 1; i <= l; i++)
{

Read station $u$ — the first station of the $i$-th metro line. The next station after $u$ is $v$.

  scanf("%d ", &u);
  while (scanf("%d%c", &v, &ch))
  {

Movement between stations is possible in both directions, and the cost of each edge is $2$.

    g[u].push_back(node(v, 2, i));
    g[v].push_back(node(u, 2, i));
    u = v;

Once the end of the line description is reached, we stop reading data for the current metro line.

    if (ch == '\n') break;
  }
}

Initialize the array for storing the shortest distances.

for (i = 1; i <= n; i++)
for (j = 1; j <= l; j++)
  dist[i][j] = 2000000000;

Read the information about the starting and destination stations. For each station, the metro line it belongs to is specified.

scanf("%d %d %d %d", &s, &line1, &f, &line2);

The algorithm starts from station $s$, located on line $line1$.

dist[s][line1] = 0;

Insert into the priority queue a node structure containing the starting vertex $s$ on line $line1$. The cost of reaching the starting vertex is $0$.

priority_queue<node, vector<node> > pq;
pq.push(node(s, 0, line1)); // (v, cost, line)
while (!pq.empty())
{

Extract from the priority queue the vertex $v$ with the minimum cost.

  int cost = pq.top().cost;
  int v = pq.top().to;
  int l1 = pq.top().line;
  pq.pop(); // dist[v][l1] = cost

Iterate over all vertices adjacent to $v$.

  for (auto edge: g[v])
  {

Consider the edge v \to to with cost $w$, which belongs to line $l2$.

    int to = edge.to;
    int w = edge.cost;
    int l2 = edge.line;

If we move along the edge v \to to, the total cost of the path becomes cost + w.

    int tot_cost = cost + w;

If vertices $v$ and $to$ belong to different lines, a transfer from line $l1$ to line $l2$ must be made.

    if (l1 != l2) tot_cost += 1;

If moving along the edge v \to to improves the current value, update dist[to][l2] and insert vertex $to$ into the queue (its total cost is $tot\_cost$, and it is located on line $l2$).

    if (tot_cost < dist[to][l2])
    {
      dist[to][l2] = tot_cost;
      pq.push(node(to, tot_cost, l2));
    }
  }
}

Print the result — the minimum travel cost to reach vertex $f$ on line $line2$.

printf("%d\n", dist[f][line2]);