هر راس رو به سه تا راس با رنگ های 1 2 3 تبدیل کن الان یه گراف داری که سه برابر گراف قبلی تعداد راس هاش و یال هاش رو هم به این صورت به هم وصل کن :

اگر راس v به راس u با رنگ c وصل بود در این صورت از راس های v که رنگشان c نیست به u ای که رنگ c دارد وصل کن اکنون در این گراف کوتاه ترین مسیر بین راس 1 و n میشه جواب اصلی(یه bfs ساده) یک مثالم میزنم تا بفهمی قضیه چیه برای مثال خودش :

که البته سوال گفته جهت داره

الان تو این گراف کوتاه ترین مسیر رو میبینی همون جوابه :) به راحتی هم خودت میتونی اثبات کنی این درسته

اینم یه کدی که قدیم من زدم برای همین کثیفه:(بدون ساختن گراف)

کد

فرض کنید K تا رنگ داریم. فرض هم می‌کنیم گراف جهت‌دار هست (اگه نیست هر یال بی‌جهتش رو با دو یال جهت‌دار جایگزین می‌کنیم)

به‌جای هر رأس v توی گراف مي یایم رئوس جدید $v_1$ الی $v_k$ رو می‌ذاریم که $v_i$ نماینده حالتی هست که به رأس v رسیده‌ایم و آخرین یالی که باهاش اومده‌ایم رنگش $i$ بوده. گراف جدید $k\times|V|$ رأس داره.

به‌ازای هر یال $v\rightarrow u$ که رنگ $x$ داشته می‌یایم یال $v_i \rightarrow u_x$ رو برای تمام $1\le i \le k$ می‌ذاریم.

حالا فقط کافیه کوتاهترین مسیر از یکی از اندیس‌های جدید رأس شروع اولیه به یکی از اندیس‌های جدید رأس پایان اولیه رو پیدا کنیم. برای سادگی کار می‌شه یه رأس جدید ساخت و به همه رئوس اندیس جدید رأس شروع اولیه وصل کرد و همین‌کار رو برای پایان هم کرد تا بخوایم فقط از یک رأس مشخص به یکی رأس مشخص دیگه بریم.

این تئوری قضیه هست. برای پیاده‌سازی می‌شه همین گراف رو به‌صورت مجازی هم ساخت به‌جای این‌که کامل بسازیمش و بعد روی SSSP بزنیم.

-- آیدین

سلام ! من سر زدن این سوال نیم ساعت صرف باگ های الکی کردم :دی مثلا اومده بودم یه مساوی نزاشته بودم یا اینکه ! نذاشته بودم هی -1 می داد :دی

حال مهم نیس !

فکر کنم اگه کد رو بزارم نفهمید چی کار کردم ولی اینو بگم برای هر راس کوتاه ترین مسیر 1 تا اون راس رو بر اساس سه حالت اینکه یال آخر از نوع 1یا2 یا 3 هستش در نظرگرفتم :د (فک نکم فهمیده باشد ) اگه کد رو ببینید می فهمید تقریبا

کد