昂貴的聘禮 http://acm.pku.edu.cn/JudgeOnline/problem?id=1062
Dijkstra算法就可以了，權非負；
有的物品對應有替代品 + 優惠價格，反過來考慮，即替代物品 + 優惠價格就達到原來的物品，建圖；
增加一個頂點，連接每個頂點，權值等于該頂點的價值，相當于你直接支付；
難點在于等級限制M； 枚舉 + 刪頂點；
因為你最后始終要到達頂點1，滿足等級限制條件還要訪問頂點 1？
一次枚舉 (lv[1] - M) ~ lv[1]，……，lv[1] ~ (lv[1] + M) ，把不符合條件的頂點給予visit[i]=1;
Stockbroker Grapevine http://acm.pku.edu.cn/JudgeOnline/problem?id=1125
考察flyod算法，先求出每個點到其他頂點的距離，然后選出其中的最大值，即為這個點到達所有頂點的最大距離；如果最大值為初始化的INF，則該點不能到達所有點；
然后再從能到達所有點中的集合點選出最小值；
Invitation Cards http://acm.pku.edu.cn/JudgeOnline/problem?id=1511
對SPFA鄰接表實現的考察，bellman_ford,dijkstra都會超時；
求每個志愿者來回的最短路，ccs -> x -> ccs,前一部分由正向圖對頂點1做一次單源最短路即可，建立逆向圖再次求解就是第二部分；
Currency Exchange http://acm.pku.edu.cn/JudgeOnline/problem?id=1860
Bellman_ford算法；從銀行實現2種貨幣的兌換可以認為每種貨幣相當于一個頂點，每家銀行相當于連接兩個頂點的一條邊；求是否存在一條路徑u -> a -> b -> …… u，權值之和大于原來的值；
MPI Maelstrom http://acm.pku.edu.cn/JudgeOnline/problem?id=1502
Heavy Transportation http://acm.pku.edu.cn/JudgeOnline/problem?id=1797
Arbitrage http://acm.hdu.edu.cn/showproblem.php?pid=1217
同HDU 1217
Frogger http://acm.pku.edu.cn/JudgeOnline/problem?id=2253
Til the Cows Come Home http://acm.pku.edu.cn/JudgeOnline/problem?id=2387
Wormholes http://acm.pku.edu.cn/JudgeOnline/problem?id=3259
Silver Cow Party http://acm.pku.edu.cn/JudgeOnline/problem?id=3268
Big Christmas Tree http://acm.pku.edu.cn/JudgeOnline/problem?id=3013
Skiing http://acm.pku.edu.cn/JudgeOnline/problem?id=3037
Candies http://acm.pku.edu.cn/JudgeOnline/problem?id=3159
Cow Hurdles http://acm.pku.edu.cn/JudgeOnline/problem?id=3615
Cow Contest http://acm.pku.edu.cn/JudgeOnline/problem?id=3660
posted on 2009-12-05 17:10
西風蕭瑟 閱讀(1983)
評論(0) 編輯 收藏 引用 所屬分類:
圖論