在遙遠的植物王國裡面，水果王國與蔬菜王國的交界處，還藏著一個神秘的地區：番茄地帶。自古以來，兩國就一直在爭論著一個問題，到底番茄屬於水果還是蔬菜？在這樣艱困的環境下，番茄地區裡面成立了一座大學：自然番茄大學（Natural Tomato University, NTU），番茄大學有一個時鐘，叫做番茄鐘，以他在每個整點、25 分，30 分，55 分會報時而聞名，據說與當年兩國交戰時的空襲時段有關。

榴槤是自然番茄大學的一名新生，由於他是水果王國的貴族，因此他在這個學期要入住自然番茄大學的豪華學生宿舍。宿舍總共有 $N$ 棟房子，由於宿舍很大，因此自然番茄大學提供了接駁車服務，接駁車總共有 $N-1$ 種固定的雙向路線，每個路線連接恰好兩棟房子，接駁車的路線設計讓任何人都有辦法透過這些接駁車從任何起點到任何終點。每次接駁要收車資 $1$ 元。

榴槤知道了宿舍的地圖，不幸的是，他忘記了他究竟要住在哪一棟房子，為了不讓其他人擔心，他決定使用這些接駁車一棟一棟確認，確認的方法就是搭接駁車到該棟房子面前並詢問管理員。一旦確認某棟房子是他要入住的地方，他便可直接入住，否則，他就必須再搭接駁車到下一棟他要確認的房子。

榴槤想要事先規劃好一條搭車的路線，讓他在最壞情況下要付的車資最少。為了先準備好該帶的錢，他找到了你，希望你能夠算出他應該至少要帶多少錢才能保證他能夠付所有車資。另外，他拿到的宿舍的地圖上的入口標記消失了，因此他不知道真正的入口在哪裡，因此榴槤想要對每個可能的入口都算出這個值。你能幫他嗎？

後來榴槤在自然番茄大學待的太開心了以致於忘了回去水果王國，這就是成語「榴槤忘返」的由來，但這又是另一個故事了。