今日打 individual 有呢題..
其實之前都見過不過唔識做
不過做左2題之後有一題勁難一題勁煩..
逼於無奈要攻呢題
題目大意 -
地球上有 N (N<=5000) 個 farm, given 它們的經度 (0..359), 有 M (M<=25000) bidirectional path 連接某些 pair farm, 行這些 path 都是以最短 (向東飛/向西飛) 方法到達
現在要環遊世界 (唔一定要 visit 所有 farm) , 「環遊」的定義為由 farm 1 開始, 行一條 path, 回到 farm 1, 而且 順時針飛行距離 不等於 逆時針飛行距離 (其實呢個唔係環遊的必要條件, 只是充分條件)
問: 最少要飛多少程
嘗試過各種 dp 的方法都失敗
BFS 又唔知幾多 states 先夠
係呢個灰暗既時刻, 突然想到把所有 node(#farm, distance difference) 扔埋入個 map .. 再開條 stl queue 硬做
諗住實 TLE, 點知.. AC!
仲要係250ms左右, 比想像中快很多
估計係因為實際狀態遠比想像中少, 同埋好多case好快就reach到終點
之後上USACO睇official solution, 都係差唔多 - -' (不過佢題解得solution code)
No comments:
Post a Comment