最初的幻想(First Fantasy，簡稱 FF)是一款由史爾庫爾(Circle)公司出品的RPG角色扮演遊戲，遊戲中有許多不同的職業，而不同的職業則可以使用不同的技能。玩家一開始使用的是初始職業─素人，而在戰鬥中獲勝取得一定的職業點數(Job Point，簡稱JP)後，即可轉職到初階職業以及其他更進階的職業，而最後的目標，即是轉職到最高階的最強職業。有些玩家喜歡存到足夠的JP，馬上就轉職到下一階的職業，而也有玩家喜歡直接存到最強職業所要的JP，再從最低階的素人直接轉職到最強職業，不過小川川發現，不管是一階一階轉上去，或是直接從素人轉到最強職業，所要花費的JP都不是最少的，因此希望你寫一個程式，幫小川川找出如何轉職才能花費最少的JP而從素人轉職到最強職業。
輸入資料的第一行有兩個正整數 N、M (3<=N<=100、1<=M<=100)，代表這遊戲中有 N 種職業，職業代號分別為 1、2、…、N，其中 1 為最初始的素人，而 N 則是最強職業。任兩種職業之間的轉職所要花費的JP為兩職業代號的差乘上100，例如 2、5 這兩個職業互轉需要的JP為 (5-2)*100=300。
除了上面提到的轉職方式稱為一般轉職外，遊戲中還有另一種轉職方式稱為特殊轉職，特殊轉職是固定兩個職業之間的互轉，所花費的JP也和一般轉職不同，輸入資料第二個正整數 M 則代表有 M 種特殊轉職的職業配對。
輸入資料第二行起有 M 行資料，每行資料有三個正整數 A、B、C，代表職業代號為 A、B 的這兩個職業之間有一種特殊轉職，其花費的JP為 C。要注意的是，特殊轉職的JP花費不一定比一般轉職來得小，而兩種職業之間可能有不止一種特殊轉職。
請輸出從職業代號為 1 的素人，轉職到代號為 N 的最強職業，所需要的 JP 最小值為多少。
3 1 1 3 180
180
5 2 1 3 150 2 4 120
320
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||