可以解决那些问题? 一般性的问题叙述 已知一个带权重的有向图G=(V,E) 和权重函数 ω:E→R (该权重函数将有向图中的每条边)映射他的权重。图中任一路径 p= <v0,v1,…,vk› 的长度就是构成该路径所有边的权重之和: 那么从结点u到结点 v的最短路径δ(u,v)被定义为: 最短路径的变体 单目的地最短路径问题 即找到从每个节点u到给定目的地结点t的最短路径。可以将图的每个边翻转,即化为了单源最短路径问题。 单结点对最短路径问题 即找到从给定结点 u到给定结点 v的最短路径。在解决结点u或者结点v的单源最短路径问题时,自然而然的解决了这个问题。 最短路径的最优子结构 最短路径算法通常依赖最短路径的一个重要性质:两个结点之间的一条最短路径包含着其他的最短路径。 解决问题需要的算法基础 最短路径估计 对于每个节点v而言,我们维持一个属性v.d,用来记录从源节点s到该节点的最短路径的上界。称v.d为s到v的最短路径估计。 除此之外,我们还维护一个属性v.π,用于指向从源节点到达该 继续阅读 >>


娄泽豪 17/05/22 19:44:05
Update 3 整个程序可以改写为以下更加简单的形式 #include<iostream> #include<iomanip> using namespace std; int main() { int a, b; while (cin >> hex >> a >> b) { cout << a + b << endl; } return 0; } —————————————————————————————— Update 2 bit_hextodec可以改写为以下更简单的形式 int bit_hextodec(char s) { if ('0' <= s && s <= '9') return s - '0'; else if ('a' <= s && s <= 'z') return s - 'a' + 继续阅读 >>


娄泽豪 17/01/17 17:22:41