cf689B题目链接

## 1681: [Usaco2005 Mar]Checking an Alibi 不在场的证明

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 250  Solved: 178
[Submit][Status][Discuss]

## Description

A crime has been comitted: a load of grain has been taken from the barn by one of FJ’s cows. FJ is trying to determine which of his C (1 <= C <= 100) cows is the culprit. Fortunately, a passing satellite took an image of his farm M (1 <= M <= 70000) seconds before the crime took place, giving the location of all of the cows. He wants to know which cows had time to get to the barn to steal the grain. Farmer John’s farm comprises F (1 <= F <= 500) fields numbered 1..F and connected by P (1 <= P <= 1,000) bidirectional paths whose traversal time is in the range 1..70000 seconds (cows walk very slowly). Field 1 contains the barn. It takes no time to travel within a field (switch paths). Given the layout of Farmer John’s farm and the location of each cow when the satellite flew over, determine set of cows who could be guilty. NOTE: Do not declare a variable named exactly ‘time’. This will reference the system call and never give you the results you really want.

谷仓里发现谷物被盗！约翰正试图从C(1≤C≤100)只奶牛里找出那个偷谷物的罪犯．幸运的是，一个恰好路过的卫星拍下谷物被盗前M(1≤M≤70000)秒的农场的图片．这样约翰就能通过牛们的位置来判断谁有足够的时间来盗窃谷物．
约翰农场有F(1≤F≤500)草地，标号1到F，还有P(1≤P≤1000)条双向路连接着它们．通过这些路需要的时间在1到70000秒的范围内．田地1上建有那个被盗的谷仓． 给出农场地图，以及卫星照片里每只牛所在的位置．请判断哪些牛有可能犯罪．

## Input

* Line 1: Four space-separated integers: F, P, C, and M * Lines 2..P+1: Three space-separated integers describing a path: F1, F2, and T. The path connects F1 and F2 and requires T seconds to traverse. * Lines P+2..P+C+1: One integer per line, the location of a cow. The first line gives the field number of cow 1, the second of cow 2, etc.

## Output

* Line 1: A single integer N, the number of cows that could be guilty of the crime.

* Lines 2..N+1: A single cow number on each line that is one of the cows that could be guilty of the crime. The list must be in ascending order.

第1行输出嫌疑犯的数目，接下来一行输出一只嫌疑犯的编号．

7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7

4
1
2
3
4

uva10986题目链接

## poj 2949 Word Rings (spfa+栈优化)

poj2949 题目链接

（E1- Ans）+（E2- Ans）+….+ （Ek- Ans）>0

/*

E1-mid + E2–mid + E3-mid + … + Ek-mid >= 0

*/

poj 1860 题目链接

1A。。。好爽啊。。。。。

poj1932题目链接

poj 1511 题目链接

## 1614: [Usaco2007 Jan]Telephone Lines架设电话线

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1325  Solved: 570
[Submit][Status][Discuss]

## Description

Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。 经过谈判，电信公司最终同意免费为FJ连结K(0 <= K < N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过 K对，那么FJ的总支出为0。 请你计算一下，FJ最少需要在电话线上花多少钱。

## Input

* 第1行: 3个用空格隔开的整数：N，P，以及K

* 第2..P+1行: 第i+1行为3个用空格隔开的整数：A_i，B_i，L_i

## Output

* 第1行: 输出1个整数，为FJ在这项工程上的最小支出。如果任务不可能完成， 输出-1

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

## Sample Output

4

FJ选择如下的连结方案：1->3；3->2；2->5，这3对电话线杆间需要的

## 1631: [Usaco2007 Feb]Cow Party

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 670  Solved: 493
[Submit][Status][Discuss]

## Description

农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

10

1A,开心。

## hdu 3790 最短路径问题 (spfa模板题)

hdu 3790 题目链接

spfa学习链接

usetc 每周算法讲堂之spfa