Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های تمرینی دوره ی تابستان:سوال ۱۴

Dijkstra

در این مسئله شما باید کوتاه‌ترین مسیر از راس ۱ به سایر راس‌های گراف را بیابید. یال‌های گراف بی‌جهت هستند.

ورودی

  • در سطر اول ورودی ابتدا n تعداد راس‌های گراف و سپس e تعداد یال‌های آن آمده است.
  • در e سطر بعدی در هر سطر ۳ عدد u و v و c نوشته شده است. این بدان معنی است که یک یال بین راس u و v با وزن c وجود دارد.
  • 1n,e105
  • 1u,vn
  • 1c104

خروجی

  • در تنها سطر خروجی n عدد چاپ کنید، که عدد iام فاصله‌ی راس 1 تا راس i را نشان می‌دهد.
  • در صورتی که مسیری از راس 1 به راس i وجود ندارد، به جای فاصله 1 چاپ کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3 1
1 2 1
0 1 -1

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه