Postacı

X pek kalabalık olmayan bir ülkedir ve farklı şehirlerin sakinleri birbirleriyle nadiren görüşmektedirler çünkü şehirler birbirine uzak olduğu icin gidip gelmek zaman almaktadır. Ve bu ülkede düzenli bir posta servisi de yoktur, yıl boyunca tüm mektup ve kargoları taşımak için bir tane postacı yeterlidir. Ancak, Noel zamanı postacının biraz daha fazla çalışması gerekmektedir. Postacı aynı anda birden fazla kargo taşıyamadığı için, X kentleri arasında gidip gelmektedir.

Haliyle postacı da kendine zaman ayırmak ister. Bunun için güzel bir plan yapması gerekmektedir. Postacı kendi şehrini terk ederek, siparişleri istediği sırayla teslim ettikten sonra yine kendi evine dönecek şekilde bir rota planlamayı ister. Postacının aklına ilk gelen isim kendi şehrinde oturan ODTÜ bilgisayar mühendisliği öğrencisi Sasha'dır.

Sasha böyle soruları derslerde çözdüklerini söyler ve istediği planlamayı yapabileceği belirtir. Ancak postacı son bir ekleme daha yapar. Kargoları dağıtmada kendi arkadaşından yardım alacağını söyler ve postacılar kendi şehirlerinden başlayarak, tüm kargoları teslim ettikten sonra yine kendi şehirlerine döndüklerinde geçen sürenin minimum olmasını ister.

Sasha'dan bu minimum sürenin ne kadar olacağını bulması istenilmektedir.

Varsayımlar

• Postacılar aynı anda sadece bir tek kargo taşıyabilmekteler.
• Teslim aldıkları kargoları teslim edecekleri şehire kadar taşımak zorundalar.
• İki şehir arasında birden fazla kargo teslimiyeti olabilir.
• Her zaman bir şehirden diğer şehire gidilebilmektedir.

Girdi (postaci.gir)

• Dosyanın ilk satırı: N (1 <= N <=100), M (1 <= M <= 10000) ve S (1 <= S <= N)
• N: Şehirlerin sayısı
• M: Çift yönlü yolların sayısı
• S: Postacıların şehiri
• Sonraki M satırda u_i v_i d_i ( 1 <= u_i, v_i <= N, 1 <= d_i <= 10000 )
• u_i ve v_i şehirlerin arasında gidip gelme d_i kadar zaman alır.
• Sonra K (1 <= K <= 15) kargo sayısı
• Sonraki K satırda (u_i, v_i)
• u_i şehirden v_i ye kargo teslimiyeti var.

Çıktı (postaci.cik)

• Ilk satırda minimum süre.

Örnek 1

postaci.gir

6 7 1
1 2 2
1 4 2
2 3 2
2 5 2
3 6 2
4 5 2
5 6 2
4
6 4
3 5
2 6
4 3

postaci.cik

16

Süre - Hareket

0 - Postacı 1 – Şehir 4’e gider

0 - Postacı 2 – Şehir 2’ye gider

2 - Postacı 1 – Kargo 4’ü alır ve Şehir 1’e, sonra Şehir 2’ye ve sonra Şehir 3’e gider

2 - Postacı 2 – Kargo 3’ü alır ve Şehir 3’e sonra da Şehir 6’e gider

6 - Postacı 2 – Kargo 3’ü teslim eder, Kargo 1’i alır sonra Şehir 5’e sonrada Şehir 4’e gider

8 - Postacı 1 – Kargo 4’ü teslim eder, Kargo 2’yi alır ve Şehir 2’ye sonrada Şehir 5’e gider

10 - Postacı 2 – Kargo 1’i teslim eder ve Şehir 1’e gider

12 - Postacı 2 – Şehir 1’e (kendi şehirleri) geri döner

12 - Postacı 1 – Kargo 2’yi teslim eder ve Şehir 2 sonrada Şehir 1 gider

16 - Postacı 1 – Şehir 1’e geri döner

Örnek 2

postaci.gir

5 9 1
1 3 4
1 5 1
2 1 5
2 3 9
2 4 4
3 4 6
3 5 2
4 5 8
5 2 3
1
4 5

postaci.cik

16

Tek kargoyu bir tane postacı teslim edecek.

Örnek 3

postaci.gir

5 7 2
1 2 7
1 3 5
1 5 2
2 4 10
2 5 1
3 4 3
3 5 4
4
1 4
5 3
5 1
1 4

postaci.cik

26