a539. CPE：Cheapest way (UVa 10436)

中等CPE

時間限制 2000 ms ・ 記憶體限制 256 MB

題目描述

運輸公司要找出最低成本路線。每公里油費為 2 taka；公車經過的每個站都需支付該站費用，包括出發站與目的站。公司另加成本的 10% 作為利潤，再除以座位數，得到每位乘客票價。

請對每個查詢找出最便宜路線與每人票價。

輸入格式

第一行是地圖數。每張地圖先有站數 n，0 < n < 20，接著 n 行各有站名與過站費。

再有道路數 m，0 < m < 20，接著 m 行各有兩個站名與距離（公里），道路可雙向通行。

最後有查詢數 q，0 < q < 10，接著 q 行各有起站、終站、座位數。地圖合法，查詢保證存在有效且唯一的最佳路線。

輸出格式

每張先輸出 Map #X，每個查詢先輸出 Query #Y，編號各從 1 開始。下一行以空白分隔列出路線的站名，再輸出 Each passenger has to pay : F taka，F 四捨五入到小數點後兩位。不同地圖的輸出之間空一行。

題目來源：UVa 10436 — Cheapest way。 原題：https://onlinejudge.org/external/104/10436.pdf

出題者： Chatgpt聯絡出題者

範例測資

範例輸入 1

2

4
mirpur12 5
farmgate 8
gulistan 10
newmarket 5
4
mirpur12 farmgate 12
mirpur12 newmarket 20
farmgate gulistan 10
newmarket gulistan 8
2
mirpur12 gulistan 30
mirpur12 newmarket 30

3
uttara 2
farmgate 8
gulistan 10
2
uttara farmgate 35
farmgate gulistan 10
1
uttara gulistan 30

範例輸出 1

Map #1
Query #1
mirpur12 farmgate gulistan
Each passenger has to pay : 2.46 taka
Query #2
mirpur12 newmarket
Each passenger has to pay : 1.83 taka

Map #2
Query #1
uttara farmgate gulistan
Each passenger has to pay : 4.03 taka
請先登入後再提交程式碼

討論與題解

載入討論區…

更多