Courses

نظریه گراف

الگوریتم دایکسترا

Module: الگوریتم دایکسترا

Problem

14 /14

ارتباط امن

Problem

با توجه به اخبار اخیر استراق سمع، دو غول اینترنتی تندرو Uragania Laim.UR و "Xenda" تصمیم به امضای توافقنامه ای برای ایجاد یک کانال ارتباطی امن بین مراکز داده یکدیگر گرفتند. n شهر در اوراگانیا وجود دارد، اما، متأسفانه، هیچ مرکز داده هر دو غول در هیچ شهری وجود ندارد. بنابراین، برای تشکیل یک کانال امن، باید خطوط ارتباطی از راه دور ایجاد شود.
متخصصان این شرکت ها تعداد جفت شهر را شناسایی کرده اند که می توان با ایجاد یک بخش کانال ارتباطی به یکدیگر متصل شوند و هزینه ایجاد چنین سگمنت را برای هر یک از این جفت ها تخمین زدند.

کانال حاصل ممکن است از چندین بخش تشکیل شده باشد. باید از یکی از شهرهایی که مرکز داده شرکت اول در آن قرار دارد شروع شود، می تواند از شهرهای میانی عبور کند و باید به شهری که مرکز داده شرکت دوم در آن قرار دارد ختم شود.
اکنون لازم است حداقل هزینه یک کانال امن برای اتصال مراکز داده دو شرکت تعیین شود.

ورودی:
خط اول شامل اعداد صحیح n و m (2 ≤ n ≤ 5000، 1 ≤ m ≤ 10⁵ ) — تعداد شهرها و تعداد جفت شهرهایی که می توانند توسط یک بخش پیوند به هم متصل شوند. خط دوم شامل n عدد صحیح ai (0 ≤ a_i ≤ 2) است. اگر a_i = 0 باشد، هیچ مرکز داده ای از هیچ یک از غول ها در شهر i وجود ندارد. اگر ai = 1، مرکز داده "Laim.UR" در شهر i قرار دارد و اگر a_i = 2، مرکز داده "Xenda" در i-ام قرار دارد. شهر . تضمین شده است که در بین این اعداد حداقل یک و یک دو وجود دارد. هر یک از خطوط m بعدی شامل سه عدد صحیح — s_i، t_i و c_i، به این معنی که شهرها s_i و t_i (1 ≤ s_i , t_i ≤ n, s_i != t_{i< /sub>) را می توان با یک بخش پیوند از هزینه ci (1 ≤ c_i ≤ 10⁵ ) متصل کرد. هر جفت شهر را می توان حداکثر با یک بخش کانال به هم متصل کرد.

خروجی:

اگر امکان اتصال دو مرکز داده از غول های اینترنتی مختلف با یک کانال ارتباطی امن وجود دارد، در فایل خروجی سه عدد x، y و d را چاپ کنید، به این معنی که می توان یک کانال ارتباطی بین شهرهای x و y ایجاد کرد. هزینه کل d. در شهر x باید یک مرکز داده "Laim.UR" وجود داشته باشد، در شهر y — مرکز داده «Xenda». اگر چندین پاسخ بهینه وجود دارد، یکی را چاپ کنید. اگر رسم کانال مورد نیاز غیرممکن است، −1.
را چاپ کنید

نمونه‌ها

<سر>

<بدن>

#
ورودی
خروجی

1
6 7

1 0 1 2 2 0

1 3 3

1 2 4

2 3 3

2 4 2

1 6 5

3 5 6

5 6 1
3 4 5

2
4 2

1 0 0 2

1 3 3

2 4 2
-1

توضیح

در مثال اول، ایجاد یک کانال ارتباطی از دو بخش بهینه است: 3 − 2 و 2 .minus; 4.}