Re: [討論] UVA 11367 Full tank 一直TLE
原文恕刪....
剛剛仔細看了一下，只要改一個地方就可以過了
修改過的版本：https://glot.io/snippets/fn534rhbpg
[43:46] 原本是無條件塞pq，不過其實只要處理cost最低的狀況就可以了
改這行大概0.910可過
我另外改了[34:40]，有以下兩個部分
第一個是 j 起始改成 std::max(top.left, weight[top.cur][i]);
相較於原本用continue加上去多少會快一些
另一個是當下一個城市油價比較便宜的時候
其實我們不用再考慮再目前的城市加超過抵達下一個城市所需的油量
因為多出來的部分，一定會比先到下個城市再加油來的貴
這兩個修改加起來，可以到0.600
實際上應該可以再縮減，因為最佳的加油油量有固定的模式 (比方說前面提到的這個)
不見得每次都要一點一點去窮舉
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.59.164 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1588684171.A.B64.html
※ 編輯: nevak (36.231.59.164 臺灣), 05/05/2020 21:12:56
推
05/08 11:59,
4年前
, 1F
05/08 11:59, 1F
推
05/08 12:00,
4年前
, 2F
05/08 12:00, 2F
討論串 (同標題文章)
完整討論串 (本文為第 2 之 2 篇)：