Aylık Programlama Sorusu - Eylül 2008

Tüm Sorularımız

Aylık programlama sorumuza gösterdiğiniz ilgi için öncelikle bütün okurlarımıza teşekkür ederiz. Ağustos ayını geride bırakırken, sizler için, gönderilen cevaplar içinden çözüm açısından en uygun olanı seçtik. Ağustos ayının en verimli ve doğru çözümünü yollayan arkadaşımız Sayın Umut Öztok'u çözümü için kutluyoruz. Kendisinin bize yollamış oldugu çözüme buradan ulaşabilirsiniz. Ayrıca bu ayki sorumuz da aşagıda açıklanmıştır. PDF versiyonu görebilmek için tıklayınız. Aylık programlama sorumuz için izlenecek yöntemi hatırlatmakta yarar var: Her ayın 1'inde dergimizle birlikte yayınlanacak sorumuzun cevaplarını, aynı ayın 20'sine kadar gönderebileceksiniz. Çözümler C/C++/Java dillerinde yazılmış olup, ayliksoru@cclub.metu.edu.tr adresine gönderilmesiyle elimize ulaşacak. En verimli ve en doğru çözümü gönderen okuyucularımız bir sonraki ay aynı sayfada duyurulacak ve bazı kod örnekleri de beraberinde yayınlanacak. Ayrıca ilerleyen aylarda sistemimizi düzene soktuktan sonra, sizlerden gelen yanıtların değerlendirilmesi sonucu aylık sorumuza en iyi cevabı gönderen arkadaşları da sürpriz ödüller bekleyecek. Her türlü sürpriz gelişme için, dergimizi düzenli olarak takip edin. Hepinize şimdiden kolay gelsin :)

METRO

Ulaşım ihtiyacını karşılamakta güçlük çeken Halka Hizmet Belediyesi kenti metro ağlarıyla örmeye karar verir. Kentin önemli merkezleri saptanır ve bu merkezlere metro durakları koymaya karar verirler. İmkanları kısıtlı olan belediye, ray masrafının en az olması için çalışmaktadır. Sizden beklediğimiz her durağa metro ulaşmak şartıyla en az maliyetle hangi noktalar arasına ray döşenmesi gerektiğini bulan bir program yazmanız.

Varsayımlar:

Durak sayısı en fazla N (2 < N < 5000) adettir.
Her bir durak kendine özgü bir tamsayı tarafından ifade edilecektir.
Duraklar arasındaki ray masrafları tamsayı olacaktır ve toplam ray masrafı “int “ veri tipini aşmayacak şekilde verilecektir.
Bazı duraklar arasına ray döşenmesi mümkün olmadığından girdide her duraktan her durağa ray masrafı verilmeyebilir.

Girdi(metro.gir):

Girdinin ilk satırında aralarında bir boşluk karakteri olmak şartıyla sırasıyla durak sayısı ve girdinin(ilk satır hariç) kaç satır olduğu verilecektir.
Geriye kalan satırlarda aralarında birer boşluk karakteriyle sırasıyla iki durak numarası ve bu iki durak arasına ray çekmenin masrafı verilecektir.

Çıktı(metro.cik):

Çıktının ilk satırına toplam ray masrafı yazılacaktır.
Sonraki satırlarda rayların hangi duraklar arasında çekilmesi gerektiği yazılacaktır.

Örnek:

metro.gir
8 10
1 2 3
1 3 8
1 7 10
2 3 14
3 4 6
3 5 5
4 5 12
5 6 9
5 7 7
7 8 15

metro.cik
53
1 2
1 3
3 4
3 5
5 6
5 7
7 8

Eray Molla

Bu derginin içeriği, Creative Commons lisansı ile korunmaktadır.
Kaynak göstermek ve link vermek şartıyla ticari olmayan amaçlarla yazılarımızı kullanabilirsiniz.