aboutsummaryrefslogtreecommitdiff
path: root/shortest_dist_road_addition1.py
diff options
context:
space:
mode:
Diffstat (limited to 'shortest_dist_road_addition1.py')
-rw-r--r--shortest_dist_road_addition1.py38
1 files changed, 27 insertions, 11 deletions
diff --git a/shortest_dist_road_addition1.py b/shortest_dist_road_addition1.py
index 0115c4a..ae40e56 100644
--- a/shortest_dist_road_addition1.py
+++ b/shortest_dist_road_addition1.py
@@ -20,20 +20,36 @@ class Solution(object):
:type queries: List[List[int]]
:rtype: List[int]
"""
- ans = []
- mp = {i: [i + 1] for i in range(n - 1)}
- for i in queries:
- mp[i[0]].append(i[1])
- dp = [float("inf")] * n
- dp[n - 1] = 0
- for j in range(n - 2, -1, -1):
- for next in mp[j]:
- dp[j] = min(dp[j], dp[next] + 1)
- ans.append(dp[0])
- return ans
+ # ans = []
+ # mp = {i: [i + 1] for i in range(n - 1)}
+ # for i in queries:
+ # mp[i[0]].append(i[1])
+ # dp = [float("inf")] * n
+ # dp[n - 1] = 0
+ # for j in range(n - 2, -1, -1):
+ # for next in mp[j]:
+ # dp[j] = min(dp[j], dp[next] + 1)
+ # ans.append(dp[0])
+ # return ans
+ sol = []
+ city_distances = {i: [-1] * i + list(range(n - i)) for i in range(n)}
+ for query in queries:
+ source, destination = query
+ city_distances[source][destination] = 1
+ for i in range(destination + 1, n):
+ city_distances[source][i] = min(
+ city_distances[destination][i] + 1, city_distances[source][i]
+ )
+ for i in range(source - 1, -1, -1):
+ city_distances[i][destination] = min(
+ city_distances[i][source] + 1, city_distances[i][destination]
+ )
+ sol.append(city_distances[0][-1])
+ return sol
if __name__ == "__main__":
obj = Solution()
print(obj.shortestDistanceAfterQueries(n=5, queries=[[2, 4], [0, 2], [0, 4]]))
print(obj.shortestDistanceAfterQueries(n=4, queries=[[0, 3], [0, 2]]))
+ print(obj.shortestDistanceAfterQueries(n=5, queries=[[1, 3], [0, 3]]))