今次的題目都不易.. 做了3題
其中一題比較有趣
G - Timetable
題目是 given 一些 node 和一個火車時間表 (departure time, arrival time), 定義一條由 1 到 n 的 optimal connection 為在 A 時由 node 1 出發而在 B 時到達 node n, 並且沒有其它方法可以在 A' (A'>=A) 時出發而在 B' (B<=B') 到達
要list出所有optimal connection
首先想到的是對所有可能的出發時間做一次shortest path, 但可能會很慢
之後想到由decreasing的departure time開始不斷做shortest path
每次行過一條edge後便可以把那條edge delete!
因為是decreasing的departure time開始做, 所以如果在t=x出發行過某條edge, 咁對於出發時間早於x, 如果是optimal的話一定不會再用那條edge
實際implement應該先把edge sort好再加進edge linked list中
不過在training時由於覺得太麻煩而沒有做這步, 不過也run得很快
你段 code 好慢架 （o:
ReplyDelete我有個 test case 你個 program 行左 8 秒...
呢題可以 O(班車) 咁做
因為 given input departure time at city i 係 sort ed
好似你咁做, 每個 city 既車用個 pointer 都係由尾掃上去就 ok
即 shortest path on cities 做 #trains at city 1 次, 但每次個 graph 既 edge set 都係 disjoint, where disjoint union = total number of trains. 用 SPFA 就做到 exactly ｜E｜ 次