Transport system#9635

Transport system (Editorial)

Let's run a breadth-first search starting from the source vertex $s$ and the destination vertex $f$ . Store the shortest distances from $s$ in the array $d i s tS$ and from $f$ in the array $d i s tF$ .

Let $o pt D i s t an ce$ optDistance denote the shortest distance between $s$ and $f$ in the original graph.

Now, let's consider the possibility of building a new road between vertices $i$ and $j$ .

When adding a road $(i, j)$ to the graph, new paths are created:

s \to i \to j \to f w i t h l e n g t h d i s tS [i] + 1 + d i s tF [j], s \to j \to i \to f w i t h l e n g t h d i s tS [j] + 1 + d i s tF [i]

s → i → j → f~with~length~distS[i] + 1 + distF[j], \\ s → j → i → f~with~length~distS[j] + 1 + distF[i]

If at least one of these distances is smaller than $o pt D i s t an ce$ optDistance, then adding the road $(i, j)$ will decrease the shortest distance between $s$ and $f$ , and thus it is not suitable.

We now need to check all possible pairs $(i, j)$ and verify if adding a new road will decrease the shortest distance between $s$ and $f$ .

Example

The graph from the first test is shown on the left. The shortest distance from vertex $1$ to vertex $5$ is $4$ . No matter which new road we add, this distance will decrease. Therefore, none of the required roads exist.

The graph from the second test is shown on the right. The shortest distance from vertex $3$ to vertex $5$ is $2$ . The possible new roads are marked with bold lines. Regardless of which of these roads we build, the distance between $3$ and $5$ will not decrease.

Algorithm implementation

Define the constant $M A X$ — the maximum possible number of vertices in the graph.

#define MAX 1001

Declare the adjacency matrix $g$ and the arrays for the shortest distances.

int g[MAX][MAX], distS[MAX], distF[MAX];

The function bfs performs a breadth-first search from the vertex $s t a r t$ . It takes the array $d i s t$ as input, where the shortest distances will be stored.

void bfs(int start, int *dist)
{

Initialize the array of shortest distances $d i s t$ .

  for (int i = 0; i <= n; i++) dist[i] = -1;
  dist[start] = 0;

Declare a queue $q$ and add the starting vertex $s t a r t$ to it.

  queue<int> q;
  q.push(start);

While the queue is not empty, dequeue the vertex $v$ .

  while (!q.empty())
  {

    int v = q.front(); q.pop();

Iterate through all vertices $t o$ adjacent to $v$ . If vertex $t o$ is not visited yet, compute the shortest distance $d i s t [t o]$ dist[to] and add it to the queue.

    for (int to = 1; to <= n; to++)
      if (g[v][to] && dist[to] == -1)
      {
        q.push(to);
        dist[to] = dist[v] + 1;
      }
  }
}

C++

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

scanf("%d %d %d %d", &n, &m, &s, &f);
memset(g, 0, sizeof(g));

Read the undirected graph.

for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = g[b][a] = 1;
}

Run a breadth-first search from vertices $s$ and $f$ . The shortest distances are stored in the arrays $d i s tS$ and $d i s tF$ , respectively.

bfs(s, distS);
bfs(f, distF);

Let $o pt D i s t an ce$ optDistance denote the shortest distance between $s$ and $f$ in the original graph.

optDistance = distS[f];

Iterate through all pairs of vertices $i$ and $j$ and consider the possibility of building a new road between them. The variable $r es$ keeps track of the number of such valid roads.

res = 0;
for (i = 1; i <= n; i++)
for (j = i + 1; j <= n; j++)

If there is no road between vertices $i$ and $j$ , compute the lengths of the shortest paths: $s \to i \to j \to f$ s → i → j → f and $s \to j \to i \to f$ s → j → i → f. If both of these distances are not less than $o pt D i s t an ce$ optDistance, then building such a road is allowed.

  if (g[i][j] == 0)
  {
     if ((distS[i] + distF[j] + 1 >= optDistance) &&
         (distS[j] + distF[i] + 1 >= optDistance))
       res++;
  }

Print the answer.

printf("%d\n", res);

Java implementation

import java.util.*;

public class Main
{
  static int g[][], distS[], distF[];
  static int n, m, s, f;
  
  static void bfs(int start, int dist[])
  {
    Arrays.fill(dist,-1);
    dist[start] = 0;

    Queue<Integer> q = new LinkedList<Integer>();
    q.add(start);

    while(!q.isEmpty())
    {
      int v = q.poll();
      for (int to = 1; to <= n; to++)
        if (g[v][to] == 1 && dist[to] == -1)
        {
          q.add(to);
          dist[to] = dist[v] + 1;
        }
    }
  }
   
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    s = con.nextInt();
    f = con.nextInt();
    
    g = new int[n+1][n+1];
    distS = new int[n+1];
    distF = new int[n+1];
    
    for (int i = 1; i <= m; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();
      g[a][b] = g[b][a] = 1;
    }

    bfs(s, distS);
    bfs(f, distF);
    
    int optDistance = distS[f];
    
    int res = 0;
    for(int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      if (g[i][j] == 0)
      {
        if ((distS[i] + distF[j] + 1 >= optDistance) &&
            (distS[j] + distF[i] + 1 >= optDistance))
          res++;
      }

    System.out.println(res);
    con.close();
  }
}

Java