一度限りの割引
Alex は都市
1 に住んでおり、都市 n に向かうことを考えています。手元にある割引クーポンを使って、フライトの総コストをできるだけ抑えたいと思っています。この割引クーポンは一回しか使えず、ルート上のいずれかのフライト料金を半額にすることができます。料金が x のフライトでクーポンを使用すると、その料金は となります。
都市 1 から都市 n までの最安ルートの料金を求めてください。入力
最初の行には、都市の数とフライトの数を表す2つの整数
n と m () が、スペース区切りで与えられます。続く
m 行にはフライトの情報が与えられます。各行には a, b, () の3つの整数がスペース区切りで記載され、これは都市 a と都市 b を結ぶ往復フライトの料金が であることを意味します。出力
都市
1 から都市 n までの最安ルートの料金を表す整数を1つ出力してください。例
Input | Output |
6 6
1 2 7
2 3 5
3 6 4
1 4 8
4 5 10
5 6 9 | 12 |
Constraints
Time limit: 5.4 seconds
Memory limit: 512 MB
Output limit: 1 MB