最短路 http://acm.hdu.edu.cn/showproblem.php?pid=2544
赤裸裸的最短路
A Walk Through the Forest http://acm.hdu.edu.cn/showproblem.php?pid=1142
"He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A." 重在理解這句話。先求出所有頂點到頂點2的最短路(以頂點2為源點做一次Dijkstra)，然后從頂點1開始記憶化搜索。
If (d[u] > d[v])
Sum += bfs(v);
Minimum Transport Cost http://acm.hdu.edu.cn/showproblem.php?pid=1385
Floyd路徑輸出，題目要按路徑的字典序輸出；
if (p[i][k] + p[k][j] == map[i][j] && path[i][k] < path[i][j])
path[i][j] = path[i][k];
即可
Arbitrage http://acm.hdu.edu.cn/showproblem.php?pid=1217
問題是是否可以盈利，如果我們把匯率看成邊，當一個點通過某些路徑返回到自己后的值大于1，則盈利；
A strange lift http://acm.hdu.edu.cn/showproblem.php?pid=1548
因為邊的權值都為1，BFS，Dijkstra都可以
一個人的旅行http://acm.hdu.edu.cn/showproblem.php?pid=2066
需要構圖，另外建立2個點，分別各乘車城市，草兒想去的地方相連，權值為0；則問題轉化為單源最短路問題；
The shortest path http://acm.hdu.edu.cn/showproblem.php?pid=2224
Bitonic path (詳見《算法導論》 P217)
一個人從p1嚴格地增的走到pn，然后再嚴格遞減的回到p1;求總路徑的最小值；
網上看到很多解題報告
看的我直冒汗
對于1 <= i <= j <= n, 我們定義P(i, j)是一條包含了P1, P2, P3 …… Pj的途徑; 這條路徑可以分成2部分：遞減序列與遞增序列，起點是Pi(1 <= i <= j)，拐點是P1，終點是Pj, P[i, j]為其最小值；那么狀態轉移方程為：
b[1,2] = |P1P2|,
i < j-1時， b[i,j] = b[i,j-1] + |Pj-1Pj| 點Pj-1在遞增序列中，
i = j-1時， b[i,j] = min{ b[k,j-1] + |PkPj|, 1<= k < j-1 } 點Pj-1在遞減序列中
b[n,n] = b[n-1,n] + |Pn-1Pn|
The Shortest Path http://acm.hdu.edu.cn/showproblem.php?pid=2807
Floyd與多次Dijkstra都可以；
A*B=C, A,C連同；
我們不妨可以對于每兩個城市相乘，把得到的矩陣跟非A，B比較，而不要對于A,C去尋找是否存在這樣一個B，結果很容易超時
另外，這里有個優化是矩陣的比較 （2維轉化成1維）
posted on 2009-12-04 17:12
西風蕭瑟 閱讀(2623)
評論(1) 編輯 收藏 引用 所屬分類:
圖論