[ Fraction ] 分數模板

今天學弟的比賽剛結束，因為有考到相關內容所以到現在才釋出分數模板。
因為每種題目要求輸出的分數格式都不一樣，所以不提供輸出的程式，必定約到最簡分數。
以下提供模板:

[ shortest path algorithm ] floyd,dijkstra,bellman,spfa 最短路徑模板

Floyd-Warshall:

Dijkstra:

Bellman-Ford:

SPFA:

[ Ternary Search ] 三分搜尋法模板

對於一個U型或倒U型函數，我們可以利用三分搜尋法找出其最低/最高點，時間複雜度為\(\ord{log \; n}\),這裡n是\(10^{(整數位數+浮點位數)}\)

關於原理就不多說了，以下提供對於U型函數的模板:

用法: