查看: 801|回復: 1

[HOJ] 15 - 搬家

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

    台南一中資訊社新手達陣程式設計達人 - 2014

    發表於 2015-3-12 17:15:38 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    原題:http://hoj.twbbs.org/judge/problem/view/15
    AC:http://hoj.twbbs.org/judge/judge/submission/31359

    好吧,我不知道正解,原本想說用floyd來做,可是遇到無向圖判環就壞掉了,所幸做了一個 [tex]O(kV^4)[/tex] 暴力來試試看就AC了,可能常數夠小吧。 因為題目中有重邊,要記得扣除留最小邊,之後枚舉所有邊[tex](i,j)[/tex],將邊[tex](i,j)[/tex]扣除後,做i到j的最短路,全部取最小就好了。

    [sojcodepad]e4360afc[/sojcodepad]
    回復

    使用道具 檢舉

  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2015-3-14 12:39:40 | 顯示全部樓層
    本帖最後由 domen111 於 2015-3-14 14:03 編輯

    這題用dijkstra快了不少,等一下再研究O(N^3)的解法

    Dijkstra: 372ms
    http://hoj.twbbs.org/judge/judge/submission/31429
    http://ideone.com/HcKeWJ

    SPFA: 558ms
    http://hoj.twbbs.org/judge/judge/submission/31410

    Bellmond-Ford: TLE
    http://hoj.twbbs.org/judge/judge/submission/31433
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復 支持 反對

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表