網頁

2014年2月27日 星期四

UVa 10308 Roads in the North

題意:
  計算該graph最遠的距離。
想法:
  DFS function 定義為"回傳該點能走的最遠深度",例如DFS(p點),則在DFS裡面我們對p點能前往的那些點做DFS,記下該路徑(route)的長度,並一直刷新route_max的大小,最後回傳route_max。
  在刷新route_max"之前",我們先把(route+route_max)與ans比較,刷新ans,(route+route_max)表示p點往兩個不同方向的路徑的和,不斷刷新ans,就能產生最遠的距離。