标签归档:SPFA

[BZOJ3482][COCI2013]hiperprostor

Orz Claris菊苣

对于这道题我们发现q很小,那么大概率是让你在线去做

然后我们知道n,m也很小,大概率是用n,m做一个dp

所以设f[i][j]表示从s出发,到达i,恰好经过jx边的最短路,利用spfa求出。

如果对于任意的i都有f[t][i]=\infty,则答案为无解。

继续阅读

[bzoj 1880][Sdoi2009]Elaxia的路线

Description

最近,Elaxia和w**的关系特别好,他们很想整天在一起,但是大学的学习太紧张了,他们 必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间,他们 希望在节约时间的前提下,一起走的时间尽可能的长。 现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图:地图上有N个路 口,M条路,经过每条路都需要一定的时间。 具体地说,就是要求无向图中,两对点间最短路的最长公共路径。

继续阅读

[bzoj 1295][SCOI2009]最长距离

Description

windy有一块矩形土地,被分为 N*M 块 1*1 的小格子。 有的格子含有障碍物。 如果从格子A可以走到格子B,那么两个格子的距离就为两个格子中心的欧几里德距离。 如果从格子A不可以走到格子B,就没有距离。 如果格子X和格子Y有公共边,并且X和Y均不含有障碍物,就可以从X走到Y。 如果windy可以移走T块障碍物,求所有格子间的最大距离。 保证移走T块障碍物以后,至少有一个格子不含有障碍物。

继续阅读