Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۲:الگوریتم ها:سوال ۳

سوال ۳

در گراف وزن دار G با n راس و m یال یک مسیر سخت مسیری است از u به v مانند u=u1,u2,,uk=v که به ازای 1ik2 داشته باشیم: w(ui,ui+1)w(ui+1,ui+2). با فرض اینکه وزن یال‌ها عددی بین 1 تا n3 است، الگوریتمی خطی (O(n+m)) ارائه دهید که طول کوتاهترین مسیر سخت از راس s به بقیه رووس در گراف G را بیابد.


ابزار صفحه