There is a team of thieves who are going to rob a bank, then escape through one of the all possible
available and then finally catch a train that is scheduled to depart from the station at a time.
In the meanwhile, the thieves are pretty sure that the cops would be following them just after the
robbery and if they reach the station before time then they will be definitely caught by the cops
need to reach the station exactly at the time 'T, catch the train and leave immediately.
Let there be 'N' cities ('0' to 'N-1') in total.
Let the robbery is to happen at the city 'X' and the station is at the city 'Y'.
You will be given the information if a city is reachable from another city and for each of these
given assume time taken to travel is 1 unit.
for eg. suppose it is given that there is a path from A to B.
Then traveling from A to B takes 1 unit of time (direct path).
Assume robbery is supposed to happen at time = 0.
Given N, X, Y, T and the path links between cities.
our task is to output the total number of ways the thieves can reach 'Y' exactly at a time
oput Format
e 1st line contains 5 space separated integers denoting N, X, Y, T, M
No of Cities
Answers
Answer:
sorry i didnt know what is the answer
Explanation:
#Python 2
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self, frm, to):
self.graph[frm].append(to)
self.graph[to].append(frm)
def checkEdge(self, frm, to):
if frm in self.graph[to] or to in self.graph[frm]:
return True
else:
return False
def getCount(self, src, dest, n):
q = deque([])
q.append([src,0])
count = 0
while(q):
vertex = q.popleft()
#print vertex
vertexname = vertex[0]
vertexdist = vertex[1]
for v in self.graph[vertexname]:
if(vertexdist+1 == n and v == dest):
count += 1
elif (vertexdist+1 < n):
q.append([v,vertexdist+1])
#print q
return count
N, X, Y, T, M = map(int, raw_input().split(" "))
gr = Graph()
for i in range(0,M):
fr, to = map(int , raw_input().split(" "))
gr.addEdge(fr,to)
res = gr.getCount(X,Y,T)
if(res == 0):
print 'not possible'
else:
print res+1
It is not completely correct but will pass most of the testcases.
#SPJ2