# Tag Archive: Graph

## Floyd–Warshall算法简介

Floyd–Warshall算法用于寻找有向图中任意两点间的最短路径，即多源最短路径。该算法可用于带负权边的图，但不能用于带负权环的图。该算法需要比较每一组节点间所有的路径，时间复杂度为Θ(|V|^3)。 　　设有一个图G，有N个节点，编号为1,2,…,N。函数shortestPath(i, j, k) 返回当仅使用点集{1,2,…,k}为中间节点时，从节点i到达节点j…

## 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…

## 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…

## Bellman-Ford算法简介

Bellman-Ford算法用于计算有向图中的单源最短路径。对于有V个顶点和E条边的图，Bellman-Ford的时间复杂度为O(V·E)，效率低于Dijkstra算法。Bellman-Ford可以用于有负权边的情况，且能判断负权环，十分灵活。 　　Wiki上给出的Bellman-Ford算法的伪代码如下所示： function BellmanFord(list vertices, list …

## 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…

## 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 …

## 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 …

## 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…

## 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 …

## 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…