ایستگاه بعدی کجاست؟

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

حداکثر 20 قسمت از جاده را در یک تقاطع معین تقسیم می‌کند. محل قرار گرفتن خانه‌ها و ایستگاه‌های آتش نشانی شبیه مورد توجه هستند که در تقاطع‌ها (چهارراه ها) واقع شده باشند.

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

به‌این ترتیب باید روشی ارائه دهیم که ایستگاه آتش‌نشانی در محلی قرار بگیرد که دسترسی به آن برای همه آسان باشد، داده‌های ورودی مساله ما از فرمت زیر پیروی می‌کنند:

1 6

2

1 2 10

2 3 10

3 4 10

4 5 10

5 6 10

6 1 10

خط اول نشان‌دهنده‌ این است که ما ? تقاطع داریم و یک ایستگاه آتش‌نشانی که در خانه شماره ? قرار دارد، و خطوط بعدی تقاطع‌ها را مشخص می‌کند، خب چگونه محل مناسب ایستگاه آتش‌نشانی را پیدا کنیم؟

بیایید فرض کنیم که ایستگاه جدید در تقاطع اول قرار می‌گیرد، حال بیاید ببینیم فاصله خانه‌های خیابان‌ها در وضعیت فعلی چطور خواهد بود؟ (البته به این نکته‌ باید توجه داشته‌باشیم که تقاطعی که در آن ایستگاه آتش‌نشانی وجود دارد محاسبه نمی‌شود.) در این حالت، تقاطع ششم با فاصله 10 کیلومتری، تقاطع پنجم با فاصله 20 کیلومتری، تقاطع چهارم با فاصله 20 کیلومتری از ایستگاه دوم، و تقاطع سوم با فاصله 10کیلومتری از ایستگاه دوم قرار می‌گیرد.

در‌واقع مجموع فواصلی که این ایستگاه‌های آتش‌نشانی پوشش می‌دهند به عدد ?? خواهیم رسید. کافی است برای بار بعدی، ایستگاه فرضی را در تقاطع سوم بگذاریم و اعداد را محاسبه کنیم. این بار نیز مجموع فواصل عدد ?? خواهد بود. برای دیگر تقاطع‌ها مقادیر زیر به‌دست می‌آید:

تقاطع چهارم: 50

تقاطع پنجم: 40

تقاطع ششم: 60

کوچکترین مجموع عدد برای هر تقاطع نشان دهنده مکان دقیق قرار گرفتن ایستگاه آتش نشانی است.

به‌عبارت دیگر در حل این مساله، همواره با گرافی مشابه با شکل زیر سر و کار داریم (این گراف با توجه به فرضیات مساله قبلی طراحی شده است.) که در آن رئوس گراف نمایانگر تقاطع‌ها و یال‌ها نمایانگر طول خیابان‌ها هستند.

وزن هر یال نیز، نمایانگر فاصله‌ای است که شهروندان تا سر تقاطع (محل قرارگیری ایستگاه آتش‌نشانی) دارند.

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

int fire_stations[n];

int num_fire_stations;

get_num_fire_stations();

foreach ( num_fire_stations) {

fire_station[n+1] = get_fire_stations();

}

for (i = 0; i « num_stations; i++) {

current_station = 0;

if (current_station != fire_station[i]) {

mark_fire_station();

results[i] = count_distances();

}}

min_result = 9999999;

for (i = 0 ; I « num_stations; i++) {

min_result = (min_result « results[i]) ? min_result: results[i];

}

امیربهاءالدین سبط‌الشیخ