المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۶۶

Ideal Path

کشور شما ‎$n$‎ شهر دارد و شما در شهر شماره ‎$1$‎ قرار دارید. هدف شما رسیدن به شهر شماره ‎$n$‎ است. بین شهرها مسیرهای هوایی وجود دارد که هر مسیر متعلق به یک شرکت هواپیمایی است. برای استفاده از یک مسیر شما باید بلیط آن مسیر را از شرکت هواپیمایی مورد نظر خریداری کنید‎. ‎

شما باید روشی ارائه دهید که با خرید کم‌ترین تعداد بلیط به شهر شماره ‎$n$‎ سفر کنید.

ورودی

  • در سطر اول ورودی دو عدد ‎$1 \leq n \leq 10^5$‎ و ‎$1 \leq m \leq 210^5$‎ نشان‌دهنده تعداد مسیرها آمده است‎.
  • در ‎$m$‎ سطر بعدی در هر سطر سه عدد ‎$(1 \leq u_i,v_i \leq n)$‎ و ‎$(1 \leq o_i \leq 10^9)$‎ آمده است که به ترتیب نشان دهنده دو شهری که بین آنها مسیر هوایی است و ‎$o_i$‎ شناسه شرکت هواپیمایی است که مسیر متعلق به آن است. تمام مسیرها دو طرفه‌اند و حتماً از شهر یک می توان به شهر ‎$n$‎ مسافرت کرد.

خروجی

در اولین سطر خروجی تعداد بلیط‌ها و در سطر بعدی شماره شرکت‌هایی که از آنها بلیط می خرید را به ترتیب خرید بنویسید‎. ‎

در صورت یکتا نبودن پاسخ سؤال، پاسخی را چاپ کنید که به ترتیب ‎lexicographically کم‌ترین است‎. ‎ ‎

محدودیت‌ها

  • محدودیت زمان: ۴ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
‎4 6‎
‎1 2 1
‎1 3 2
3 4 3‎
‎2 3 1‎
2 4 4
‎3 1 1‎
2‎
‎1 3‎

پاسخ

اگر هر شرکت هواپیمایی را معادل یک رنگ در نظر بگیریم، مسئله از ما مسیری می‌خواهد که در آن کم‌ترین تعداد تغییر رنگ را داشته باشیم. در ادامه راه‌حل، هر شرکت هواپیمایی را معادل با یک رنگ فرض می‌گیریم‎.

‎ در هر قسمت از مسیر که قرار داشته باشیم، برای ما تنها چیزهایی که مهم است، این است که در چه رأسی قرار داریم و با چه یالی به این رأس وارد شده‌ایم. بنابراین اگر بخواهیم این مسئله را با روش پویا یا چیزی مشابه آن حل کنیم، می‌توانیم هر وضعیت را با یک زوج مرتب مثل ‎$(v‎, ‎c)$‎ نشان دهیم که ‎$v$‎ شماره ی رأس و ‎$c$‎ رنگ بلیطی است که به آن رأس وارد شده‌ایم. هنگام تغییر از یک وضعیت به وضعیت دیگر در صورتی که تغییر رنگ دهیم، باید ‎1‎ واحد هزینه بپردازیم و در غیر این صورت، هزینه‌ای نباید بپردازیم. بنابراین مسئله به یافتن کوتاه‌ترین مسیر از وضعیت ‎$(1‎, -‎1)$‎ به وضعیت ‎$(n‎, ‎*)$‎ در گراف وضعیت‌ها تبدیل می‌شود. رنگ -‎1‎ نشان‌دهنده‌ی این است که با رنگ مشخصی وارد رأس یک نشده‌ایم. و منظور از ‎$(n‎, ‎*)$‎ این است که با هر رنگی می‌توان مسیر را در رأس ‎$n$‎ تمام کرد. این روش دومشکل دارد: ‎

  1. ‎گراف وضعیت‌ها دور دارد، و با روش پویا نمی‌توان کوتاه‌ترین مسیر را پیدا کرد.
  2. ‎ تعداد وضعیت‌ها برابر تعداد رنگ‌ها ضرب در تعداد شهرهاست که بسیار زیاد است و همچنین تعداد یال‌های بین وضعیت‌ها می‌تواند بسیار زیاد باشد.

‎ ‎ برای حل مشکل اول، می‌توان به جای استفاده از روش پویا، از الگوریتم‌های ‎BFS‎ یا ‎Dijkstra‎ برای یافتن کوتاه‌ترین مسیر استفاده کرد. اما برای رفع مشکل دوم باید تعداد وضعیت‌ها و یال‌های بین آن‌ها را کاهش دهیم. اولا توجه کنید که برای یک وضعیت مثل ‎$(u,c)$‎ در صورتی که در گراف ورودی به رأس ‎$u$‎ یالی به رنگ ‎$c$‎ متصل نباشد، این وضعیت اصلا قابل دسترسی نیست. بنابراین کافی است فقط وضعیت‌هایی مثل ‎$(u‎, ‎c)$‎ را در نظر بگیریم که در گراف ورودی رأس ‎u‎ یالی به رنگ ‎$c$‎ داشته باشد و به سادگی می‌توان نشان داد که تعداد این وضعیت‌ها حداکثر برابر ‎$m$ (تعداد یال های گراف ورودی) است‎.

اما هم‌چنان با مشکل تعداد زیاد یال‌ها مواجه هستیم. فرض کنید در گراف رأسی مثل ‎$v$‎ وجود دارد که به آن ‎$t$‎ یال با رنگ‌های مختلف متصل است. در نتیجه به ازای هر کدام از این رنگ‌ها مثل ‎$c$‎ یک وضعیت ‎$(v‎ , ‎c)$‎ در گراف وضعیت‌ها داریم و همه‌ی این وضعیت‌ها به هم متصل هستند. بناربراین در حدود ‎t2‎ یال به ازای این رأس وجود دارد. و این تعداد می تواند بسیار زیاد باشد. برای حل این مشکل می‌توان به ازای هر رأس مثل ‎u‎ یک وضعیت دیگر به اسم ‎$(u‎, -‎1)$‎ گرفت که به معنی تغییر رنگ باشد. به این شکل که از هر وضعیت مثل ‎$(u‎, ‎c)$‎ در صورتی که نخواهیم تغییر رنگ دهیم فقط به وضعیت‌هایی مثل ‎$(v‎, ‎c)$‎ می توان رفت، به شرطی که در گراف ورودی بین رئوس ‎$u$‎ و ‎$v$‎ یالی با رنگ ‎$c$‎ وجود داشته باشد و در صورتی که بخواهیم تغییر رنگ بدهیم به وضعیت ‎$(u‎, -‎1)$‎ می رویم و یک واحد هزینه می‌پردازیم. به سادگی می‌توان نشان داد که با این روش تعداد یال‌ها در گراف وضعیت ها از ‎$O(m)$‎ یعنی تعداد یال‌های گراف ورودی است‎.

‎ پس می‌توان در گراف وضعیت‌ها با الگوریتمی مثل Dijkstra کوتاه‌ترین مسیر بین وضعیت‌های ‎$(1‎, -‎1)$‎ و ‎$(n‎, ‎*)$‎ پیدا کرد. و در نهایت با اندکی تغییر در الگوریتم ‎Dijkstra‎ می‌توان کاری کرد که مسیر نهایی از نظر lexicographically‎ هم بهینه باشد‎.‎

پيچيدگي

با توجه به اینکه شماره‌ی رنگ‌ها تا ‎$10^9$‎ مقدار می‌تواند داشته باشد، برای نگهداری وضعیت‌ها می‌توان از map یا set‎ استفاده کرد، که این کار باعث می‌شود هنگام دسترسی به هر وضیعت از ‎$O(\log m)$‎ زمان صرف کنیم. الگوریتم ‎Dijkstra‎ نیز از ‎$O(m \log m)$‎ زمان صرف می‌کند، زیرا در گراف وضعیت‌ها هم تعداد رئوس و هم تعدا یال‌ها از ‎$O(m)$‎ است. بنابراین می توان الگوریتم را با پیچیدگی ‎$O(m \log m)$‎ پیاده‌سازی کرد.


ابزار صفحه