時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
Daniel 可在家向 Amazon 購買 DVD，也可開車到特定商店以較低價格購買。每張 DVD 只在一間商店有已知優惠，他可選擇任意部分優惠，也可不出門。道路是雙向的，通行成本代表油錢；行程必須從編號 0 的家出發，最後回家。求總折扣減去行車成本後，最多可節省多少錢。
輸入格式
第一行為情境數，每個情境前有空白行。每筆先給商店數 N（1 ≤ N ≤ 50）、道路數 M（1 ≤ M ≤ 1000）。接著 M 行給兩端編號與道路成本（美元，兩位小數）。商店編號 1 至 N，保證皆可從家到達。再給 DVD 數 P（1 ≤ P ≤ 12），接著 P 行給優惠商店編號及該 DVD 可省金額（兩位小數）。
輸出格式
能淨省正金額時輸出 Daniel can save $D.CC，固定兩位小數；否則輸出 Don't leave the house。
來源：UVa 11284 — Shopping Trip。本敘述依原題規格重新撰寫。
範例測資
範例輸入 1
2 4 5 0 1 1.00 1 2 3.00 1 3 2.00 2 4 4.00 3 4 3.25 3 2 1.50 3 7.00 4 9.00 1 1 0 1 1.50 1 1 2.99
範例輸出 1
Daniel can save $3.50 Don't leave the house
請先登入後再提交程式碼
討論與題解
載入討論區…