whust 2016 warm up E ||codeforces 689 B. Mike and Shortcuts (spfa)

cf689B题目链接

题意:n点。。点i到点j的代价是|i-j|..给出n条近路。。。a[i]表示点i到a[i]的代价为1(注意近路不一定就近)

思路:一开始建边卡了一下。。。实际上只要连相邻的就好了。。。然后边表只开了2*N蠢哭。。。实际上应该3*M…因为连相邻的边是双向的。。。再加上近路的单向。。。然后spfa就好了。。。。

 

 

 

 

hdu 3873 Invade the Mars (有限制条件的最短路。。)

hdu3873题目链接

题意:n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。

思路:。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。。所以还是上dij吧。。。

然后dij写得比较少。。。不是很熟练。。参考了这篇题解参考题解

思路倒是不难想,我在写spfa的时候也是这样想法,然后试图记录路径递归来搞。。。。。然而并不可以2333

也是第一次遇到带限制条件的最短路。。。还是多积累吧。。。

哦对了。。。权值比较大。。。要记得开long long

 

 

 

BZOJ 1681: [Usaco2005 Mar]Checking an Alibi 不在场的证明 (spfa)

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.

第1行输入四个整数F,只C,和M;

接下来P行每行三个整数描述一条路,起点终点和通过时间.

接下来C行每行一个整数,表示一头牛所在的地点.

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行输出嫌疑犯的数目,接下来一行输出一只嫌疑犯的编号.

Sample Input

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

Sample Output

4
1
2
3
4

HINT

 

思路: 非常显然的最短路。。。。一个月没写代码还能1A…感动

 

 

BZOJ 1631: [Usaco2007 Feb]Cow Party (SPFA)

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牛棚参加派对还是返回住所,她们都采用了用时最少的路线.那么,用时最多的奶牛需要多少时间来回呢?

Input

第1行:三个用空格隔开的整数.

第2行到第M+1行,每行三个用空格隔开的整数:Ai, Bi,以及Ti.表示一条道路的起点,终点和需要花费的时间.

Output

唯一一行:一个整数: 所有参加聚会的奶牛中,需要花费总时间的最大值.

Sample Input

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

Sample Output

10

HINT

样例说明:
共有4只奶牛参加聚会,有8条路,聚会位于第2个农场.
第4只奶牛可以直接到聚会所在地(花费3时间),然后返程路线经过第1和第3个农场(花费7时间),总共10时间.

思路:想了一下。。因为要知道每个点到x的最短距离。。。以及反过来。。

单向很容易知道。。。以x点为起点做一遍spfa,那么x到每个点的最短距离就知道了。。

那么反过来怎么办呢?

我的做法是反向建边再跑一遍spfa…

1A,开心。

 

 

codeforces #333 div 2 C. The Two Routes

http://codeforces.com/problemset/problem/602/C
题意:给出n个城镇,m条双向铁路,对于任意不同的x,y,如果x,y之间没有铁路,那么一定有双向公路。train只能走铁路,bus只能走公路。现在一辆火车和一辆bus同时从1出发,要到达n,处于安全考虑,bus和火车不能同时处在除了n以外的点。bus和train不要求同时到达。任意一段道路的时间花费都是1小时。问最少需要多久使得bus和train都到达n。如果存在某个不能到达,那么输出-1.
思路:n才400.一开始打算先按照rail和road建两个图。这两个图互为补。然后在floyd的时候加以判断。但是马上就发现。。不能同时到达同伙一个点这个条件其实不会影响。。因为按照题意,一定存在一条1到n的路,不是公路就是铁路。那么就让有路的花费1的代价到n,然后剩下的求一个一到n的最短路即可。由于n才400.。最短路怎么搞都行。。我偷懒就用floyd了。