+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت --- نقشه متروی تهران را در نظر بگیرید. (این عکس فقط برای دادن یک دید کلی به شماست و نیازی به خواندن کلمات آن نیست.)  اسم تمام ایستگاه‌ها در [این فایل](https://quera.org/qbox/view/78bGocfPql/metro.txt) در ۷ سطر آمده است. در سطر $i$ام، نام ایستگاه‌های خط $i$ام مترو به ترتیب و با فاصله آمده است. (توجه کنید نام یک ایستگاه شامل کاراکتر فاصله (*space*) نیست.) + زمان لازم تردد قطار بین دو ایستگاه ۲ دقیقه + زمان لازم برای ورود به ایستگاهی که قصد سوار شدن قطار را داریم، ۱۷ دقیقه + زمان لازم برای خارج شدن از ایستگاه که قصد پیاده زدن در آن را داریم، ۱۲ دقیقه. + زمان لازم برای تعویض خط نیاز داریم، نیز ۱۰ دقیقه است. توجه کنید در ایستگاه‌هایی که محل تقاطع دو خط هستند، می‌توان از طریق هر دو خط سوار شد و نیازی به معطلی برای تعویض خط نداریم. محسن می‌خواهد خریدهای خودش را از دیجیکالا انجام ندهد و با مترو برود و خرید کند. او بعد از مسیریابی فهمید که باید از ایستگاه $s$ سوار مترو شود و در ایستگاه $f$ پیاده شود. از شما می‌خواهیم برنامه‌ای بنویسید که کمترین زمانی که طول می‌کشد تا محسن به محل خرید برسد را محاسبه کنید. # ورودی در سطر اول ورودی عدد صحیح و مثبت $q$ آمده است. $$ 1 \leq q \leq 16000 $$ در $q$ سطر بعدی در هر سطر دو رشته $s$ و $f$ آمده که نام ایستگاه شروع و پایان را نشان می‌دهد. تضمین می‌شود این دو رشته در فایل ایستگاه‌ها موجوداند. # خروجی برای هر کدام از $q$ جفت ایستگاه ورودی داده شده، کمینه زمان لازم برای رسیدن از ایستگاه مبدا به ایستگاه مقصد را محاسبه کنید. # مثال ## ورودی نمونه ۱ ``` 5 Tajrish Gheytariyeh Tajrish Gholhak Tarasht Eram-e_Sabz Aghdasiyeh Sohrevardi Towhid Baharestan ``` ## خروجی نمونه ۱ ``` 31 35 43 45 51 ``` ---------- سفر اول از «تجریش» به «قیطریه»: + ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «تجریش» طول می‌کشد. + ۲ دقیقه طول می‌کشد تا در خط ۱، از ایستگاه «تجریش» به «قیطریه» برسد. + ۱۲ دقیقه طول می‌کشد تا از ایستگاه «قیطریه» خارج شود. بنابراین مجموع زمان این سفر برابر است با: $$17 + 2 + 12 = 31$$ ---------- سفر دوم از «تجریش» به «قلهک»: + ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «تجریش» طول می‌کشد. + ۶ دقیقه طول می‌کشد تا در خط ۱، از ایستگاه «تجریش» به «قلهک» برسد. + ۱۲ دقیقه طول می‌کشد تا از ایستگاه «قلهک» خارج شود. بنابراین مجموع زمان این سفر برابر است با: $$17 + 6 + 12 = 35$$ ---------- سفر سوم از «طرشت» به «ارم سبز»: + ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «طرشت» طول می‌کشد. + ۲ دقیقه طول می‌کشد تا در خط ۲، از ایستگاه «طرشت» به «تهران (صادقیه)» برسد. + ۱۰ دقیقه طول می‌کشد تا از خط از ۲ به ۵ در ایستگاه «تهران (صادقه)» تغییر مسیر بدهد. + ۲ دقیقه طول می‌کشد تا در خط ۵، از ایستگاه «تهران (صادقیه)» به «ارم سبز» برسد. + ۱۲ دقیقه طول می‌کشد تا از ایستگاه «ارم سبز» خارج شود. بنابراین مجموع زمان این سفر برابر است با: $$17 + 2 + 10 + 2 + 12 = 43$$ ---------- سفر چهارم از «اقدیسه» به «سهروردی»: + ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «اقدسیه» طول می‌کشد. + ۱۶ دقیقه طول می‌کشد تا در خط ۳، از ایستگاه «اقدسیه» به «سهروردی» برسد. + ۱۲ دقیقه طول می‌کشد تا از ایستگاه «سهروردی» خارج شود. بنابراین مجموع زمان این سفر برابر است با: $$17 + 16 + 12 = 45$$ ---------- سفر پنجم از «توحید» به «بهارستان»: + ۱۷ دقیقه ورود و سوار قطار شدن در ایستگاه «توحید» طول می‌کشد. + ۱۰ دقیقه طول می‌کشد تا در خط ۴، از ایستگاه «توحید» به «دروازه شمیران» برسد. + ۱۰ دقیقه طول می‌کشد تا از خط از ۴ به ۲ در ایستگاه «دروازه شمیران» تغییر مسیر بدهد. + ۲ دقیقه طول می‌کشد تا در خط ۵، از ایستگاه «دروازه شمیران» به «بهارستان» برسد. + ۱۲ دقیقه طول می‌کشد تا از ایستگاه «بهارستان» خارج شود. بنابراین مجموع زمان این سفر برابر است با: $$17 + 10 + 10 + 2 + 12 = 51$$

حل سؤال در بانک سؤالات