- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
نقشه متروی تهران را در نظر بگیرید. (این عکس فقط برای دادن یک دید کلی به شماست و نیازی به خواندن کلمات آن نیست.)
اسم تمام ایستگاه‌ها در این فایل در ۷ سطر آمده است. در سطر $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$$
ارسال پاسخ برای این سؤال