bugbuster404's blog

By bugbuster404, history, 3 years ago, In English

I have been trying this for a long time but still getting WA on test 22 (onwards)

Problem

Basically you are given an undirected graph consisting of n vertices and m edges where every edge has weight=1. The distance between two vertices is equal to the minimum possible number of edges on a path between them.

There are given two vertices S and T . You have to select two vertices u and v (where u and v don't have a direct edge) such that joining them DOES NOT decrease the distance between S and T. We have to print how many such distinct unordered pairs exist...

...

I ran BFS two times and found the shortest distance of every vertices from S and T and used the following relation to find whether u and v should be added or not:-

if ((distance_s[u] + distance_t[v] + 1 < distance_s[t]) || (distance_s[v] + distance_t[u] + 1 < distance_s[t]))

Here is the entire code :-

Spoiler

Everytime I am getting WA on test 22. Its calculating less than the actual value. Plz help which cases I am missing

Thx :)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it