شنگدباو در فراق یار و نبود کار حوصلهاش سر رفته بود و تصمیم به حل سوالی گرفت. صورت سوال…
- User
شنگدباو در فراق یار و نبود کار حوصلهاش سر رفته بود و تصمیم به حل سوالی گرفت. صورت سوال طولانی بود. به قول یکی از دوستان شنگدباو «همیشه که نباید سوالا رو پیچوند! بعضی وقتا باید ساده حرف زد!» در نتیجه تصمیم گرفت حالت ساده شدهی صورت سوال را قرار دهد:
تعداد n n رشته داده شده است، رشتهی i iام s i s i میباشد. به ازای هر رشته لیستی از اعداد موجود است، لیست متناظر با رشتهی i iام شامل ∣ s i ∣ + 1 ∣s i ∣+1 عدد است که عدد j jام آن (با شروع از صفر) مقدار a i , j a i,j دارد. ( 1 ≤ i ≤ n 1≤i≤n ، 0 ≤ j ≤ ∣ s i ∣ 0≤j≤∣s i ∣)
هزینهی رفتن از رشتهی s i s i به s j s j برابر است با a j , l c p ( s i , s j ) a j,lcp(s i ,s j ) (منظور از l c p ( s , p ) lcp(s,p) طول بزرگترین پیشوند مشترک دو رشتهی s s و p p است)
فرض کنید روی رشتهی s A s A قرار داریم و میخواهیم به رشتهی s B s B برسیم. کمینه هزینه برای انجام این کار را باید خروجی دهید.»
شنگدباو سوال را حل کرده است! آیا شما هم میتوانید آن را حل کنید؟
ورودی در سطر اول ورودی عدد n n داده شده است. سپس در 2 × n 2×n سطر بعدی ابتدا رشتهی ناتهی i i ام آمده است و سپس لیست متناظر با رشتهی مورد نظر آمده است. در سطر آخر نیز ۲ عدد آمده است که اولی A A و دومی B B است.
1 ≤ n ≤ 500
000 1≤n≤500 000 0 ≤ a i , j ≤ 1 0 9 0≤a i,j ≤10 9
∑ ∣ s i ∣ ≤ 500
000 ∑∣s i ∣≤500 000 A ≠ B A =B
رشته های ورودی از حروف کوچک الفبا تشکیل شدهاند. خروجی در تنها سطر خروجی کمترین هزینه برای رفتن از s A s A به s B s B را خروجی دهید.
زیر مسئلهها زیرمسئله نمره محدودیت ۱ ۲۰ n ≤ 5
000 n≤5 000 ۲ ۲۰ به ازای هر 0 ≤ j < a b s ( s i ) 0≤j<abs(s i ) داریم: a i , j + 1 − a i , j
1 a i,j+1 −a i,j =1 ۳ ۲۰ رشتهها فقط از حروف a a و b b تشکیل شده اند. ۴ ۴۰ بدون محدودیت اضافی مثال ورودی نمونه ۱ 3 a 0 1 b 0 1 a 0 1 1 3 Plain text خروجی نمونه ۱ 0 Plain text ورودی نمونه ۲ 3 abcd 0 1 2 3 4 abc 0 1 2 3 abcde 0 1 2 10 1 2 2 3 Plain text خروجی نمونه ۲ 4 Plain text ورودی نمونه ۳ 4 shengdebao 10 11 12 13 14 15 16 17 18 19 20 bao 4 3 2 7 barricade 1 13 12 11 10 9 8 7 6 5 baran 7 14 3 14 7 6 1 4 Plain text خروجی نمونه ۳ 6 java
- Assistant
The problem is to find the minimum cost to reach from string
s_Atos_B, where the cost froms_itos_jisa_j, lcp(s_i,s_j), withlcp(s_i,s_j)being the length of the longest common prefix ofs_iands_j.Given the large constraints, we can't consider all possible pairs of strings. Instead, we can model the problem using Dijkstra's algorithm on a trie (prefix tree) of all the strings.
Here's how you can solve the problem:
-
Build a Trie:
- Construct a trie from all input strings. Each node represents a prefix.
-
Initialize Distances:
- For each node (prefix) in the trie, initialize the distance
dist[p]to infinity (INF), except for the starting strings_A, wheredist[s_A] = 0.
- For each node (prefix) in the trie, initialize the distance
-
Dijkstra's Algorithm:
- Use a priority queue to perform Dijkstra's algorithm.
- At each step, pop a node
pwith the smallestdist[p]from the queue. - For each neighbor
p'ofp(which can be the parent or children in the trie), ifdist[p'] > dist[p], updatedist[p'] = dist[p]and pushp'onto the queue. - Important: If
pcorresponds to a complete strings_i(i.e., it's a leaf node), add the costa_i, |p|todist[p]if it hasn't been added before.
-
Track Visited Strings:
- Maintain a set to keep track of strings (leaf nodes) for which you've already added the cost to avoid adding the cost multiple times.
-
Termination:
- Continue the algorithm until the priority queue is empty or until you reach
s_B. - The minimum cost to reach
s_Bwill bedist[s_B].
- Continue the algorithm until the priority queue is empty or until you reach
-
Output:
- Print the minimum cost to reach from
s_Atos_B.
- Print the minimum cost to reach from
Here's the code that implements the above approach:
from collections import defaultdict import sys import threading import heapq def main(): import sys sys.setrecursionlimit(1 << 25) input = sys.stdin.readline n = int(sys.stdin.readline()) trie = {} end_nodes = {} a_values = {} class Node: def __init__(self): self.children = {} self.parent = None self.char = '' self.is_end = False self.a_i = [] self.dist = float('inf') root = Node() strings = [] for _ in range(n): s = sys.stdin.readline().strip() s_node = root for c in s: if c not in s_node.children: child = Node() child.parent = s_node child.char = c s_node.children[c] = child s_node = s_node.children[c] s_node.is_end = True strings.append(s_node) a_i = list(map(int, sys.stdin.readline().strip().split())) a_values[s_node] = a_i A_str, B_str = map(int, sys.stdin.readline().strip().split()) s_A = strings[A_str -1] s_B = strings[B_str -1] visited_strings = set() import heapq hq = [] s_A.dist = 0 heapq.heappush(hq, (s_A.dist, s_A)) while hq: dist_u, u = heapq.heappop(hq) if u.dist < dist_u: continue if u == s_B and u.is_end: print(int(u.dist)) return if u.is_end and u not in visited_strings: # Add cost a_i,|u| a_i = a_values[u] u.dist += a_i[len(a_i)-1] visited_strings.add(u) for v in u.children.values(): if v.dist > u.dist: v.dist = u.dist heapq.heappush(hq, (v.dist, v)) if u.parent: v = u.parent if v.dist > u.dist: v.dist = u.dist heapq.heappush(hq, (v.dist, v)) # If s_B is not reachable print(int(s_B.dist)) threading.Thread(target=main).start()This code handles the problem within the constraints and efficiently calculates the minimum cost without considering all possible pairs of strings.
-