最短路 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
西风萧瑟 阅读(2610)
评论(1) 编辑 收藏 引用 所属分类:
图论