There are N cities and two newly built cities X and Y among them (1 <=X<=Y<= N) There exists a road between cities:
i and i+1 for each 1 to N
X and Y.
The task is to tell for each k from 1 to N, the number of pairs of cities (such that the shortest path between city i and city is k
Consider the following example.
N number of cities-3
X, first special city-1
Y second special city-3
The pair of cities having the shortest distance-1 are (1,2) (1,3) and (2,3)
There is no pair of cities with the shortest distance-2.
There is no pair of cites with the shortest distance-2
Hence the answer returned is (3,0,0)
Can someone explain how to approach this problem?
What? I can't understand the statement at all. Can you rephrase it?
Probably this:
You're given a graph with $$$n$$$ vertices indexed $$$1 \ldots n$$$. The graph has $$$n$$$ edges: an edge between $$$i$$$ and $$$i + 1$$$ for every $$$1 \le i < n$$$ and an extra edge between $$$x$$$ and $$$y$$$ for given $$$x$$$ and $$$y$$$.
For each $$$k$$$ in $$$1 \ldots n$$$, calculate the number of pairs $$$(u, v)$$$ such that the length of the shortest path between $$$u$$$ and $$$v$$$ is $$$k$$$.
Ah thanks
Draw the graph like this: a bamboo
Unable to parse markup [type=CF_MATHJAX]
with the additional cycleUnable to parse markup [type=CF_MATHJAX]
We can split the vertices into the three sets
Unable to parse markup [type=CF_MATHJAX]
and the cycleUnable to parse markup [type=CF_MATHJAX]
It is easy to calculate the contributions from a bamboo graph
Unable to parse markup [type=CF_MATHJAX]
There areUnable to parse markup [type=CF_MATHJAX]
pairs with distance $$$d.$$$ And note that the shortest path between a vertex in $$$A$$$ and $$$B$$$ never uses other edges inUnable to parse markup [type=CF_MATHJAX]
So we can easily compute for $$$\{u,v\}$$$ withUnable to parse markup [type=CF_MATHJAX]
Second case is
Unable to parse markup [type=CF_MATHJAX]
This is also easy to do in $$$O(n).$$$ If cycle length is $$$j$$$ then there are exactly $$$j$$$ pairs with distance $$$d$$$ for eachUnable to parse markup [type=CF_MATHJAX]
Final case is
Unable to parse markup [type=CF_MATHJAX]
orUnable to parse markup [type=CF_MATHJAX]
SupposeUnable to parse markup [type=CF_MATHJAX]
Clearly shortest path never uses any vertices in $$$B.$$$ Then for $$$d=1$$$ there is only one pair,Unable to parse markup [type=CF_MATHJAX]
For $$$d=2$$$ there areUnable to parse markup [type=CF_MATHJAX]
pairs,Unable to parse markup [type=CF_MATHJAX]
Similarly for $$$d=3$$$ there areUnable to parse markup [type=CF_MATHJAX]
pairs, ie.Unable to parse markup [type=CF_MATHJAX]
and so forth.Overall solution runs in $$$O(n).$$$
Could you provide more detailed for this ?
some pseudocode or something