Floyd–Warshall算法简介
Floyd–Warshall算法用于寻找有向图中任意两点间的最短路径，即多源最短路径。该算法可用于带负权边的图，但不能用于带负权环的图。该算法需要比较每一组节点间所有的路径，时间复杂度为Θ(|V|^3)。 设有一个图G，有N个节点，编号为1,2,…,N。函数shortestPath(i, j, k) 返回当仅使用点集{1,2,…,k}为中间节点时，从节点i到达节点j…
Read more
URAL 1416. Confidential
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1416 1416. Confidential Time limit: 2.0 second Memory limit: 64 MB Zaphod Beeblebrox — President of the Imperial Galactic Government. And by chan…
Read more
POJ 3259. Wormholes
1. 题目 http://poj.org/problem?id=3259 Wormholes Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 36967 Accepted: 13562 Description While exploring his many farms, Farmer John has discovered a…
Read more
Bellman-Ford算法简介
Bellman-Ford算法用于计算有向图中的单源最短路径。对于有V个顶点和E条边的图，Bellman-Ford的时间复杂度为O(V·E)，效率低于Dijkstra算法。Bellman-Ford可以用于有负权边的情况，且能判断负权环，十分灵活。 Wiki上给出的Bellman-Ford算法的伪代码如下所示： function BellmanFord(list vertices, list …
Read more
URAL 1643. Attack of the Dark Fortress
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1643 1643. Attack of the Dark Fortress Time limit: 1.0 second Memory limit: 64 MB Knowing that lich Sandro left to fight the King of Hell, Erathi…
Read more
URAL 1329. Galactic History
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1329 1329. Galactic History Time limit: 1.0 second Memory limit: 64 MB It is very hard for one person to learn all galactic history. But, on the …
Read more
URAL 1280. Topological Sorting
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1280 1280. Topological Sorting Time limit: 1.0 second Memory limit: 64 MB Michael wants to win the world championship in programming and decided …
Read more
URAL 1198. Jobbery
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1198 1198. Jobbery Time limit: 2.0 second Memory limit: 64 MB Hard times came for Martian senate. Even this pride of Martian democracy can not op…
Read more
URAL 1162. Currency Exchange
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1162 1162. Currency Exchange Time limit: 1.0 second Memory limit: 64 MB Several currency exchange points are working in our city. Let us suppose …
Read more
URAL 1254. Die Hard
1. 题目 http://acm.timus.ru/problem.aspx?space=1&num=1254 1254. Die Hard Time limit: 5.0 second Memory limit: 64 MB There is a city with a grid of square blocks of the N × M size. There are building…
Read more