/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=2377
Name : 2377 Bus Pass
Date : Tuesday, January 24, 2012
Time Stage : 2 hours
Result:
5290124 2012-01-24 15:02:29 Accepted 2377
375MS 2692K 2336 B
C++ pyy
5289711 2012-01-24 12:12:48 Wrong Answer 2377
375MS 2692K 2292 B
C++ pyy
5289706 2012-01-24 12:07:45 Wrong Answer 2377
390MS 2692K 2282 B
C++ pyy
Test Data :
Review :
话说这题确实是没有思路,只好参考了大牛的代码,原来可以这样做~
大牛题解:http://blog.csdn.net/popopopolo/article/details/6432852
//----------------------------------------------------------------------------*/
#include <cstdio>
#include <CSTRING>
#include <queue>
using namespace std ;
#define MEM(a, v) memset (a, v, sizeof (a)) // a for address, v for value
#define INF (-1)
#define MAXN 10000
struct EDGE {
int v, w, next ;
} ;
bool used[MAXN] ;
int nz, nr, edgeCnt ;
int first[MAXN], max_d[MAXN], dist[MAXN] ;
EDGE edge[20*MAXN] ;
void add (const int u, const int v, const int w)
{
edge[edgeCnt].v = v ;
edge[edgeCnt].w = w ;
edge[edgeCnt].next = first[u] ;
first[u] = edgeCnt++ ;
}
void spfa (const int beg)
{
int i, d, u, v ;
queue<int> q ;
MEM (dist, INF) ;
MEM (used, 0) ;
// 这里不加就WA,考验思维缜密度,搞程序的一定要细心啊!
// 真心不明白为什么要加这里,求解释!
if (max_d[beg] == INF)
max_d[beg] = 1 ;
dist[beg] = 1 ;
used[beg] = 1 ;
q.push (beg) ;
while (!q.empty ())
{
u = q.front () ;
q.pop () ;
used[u] = 0 ;
for (i = first[u] ; i != -1 ; i = edge[i].next)
{
d = dist[u] + edge[i].w ;
v = edge[i].v ;
if (dist[v] == INF || dist[v] > d)
{
dist[v] = d ;
if (max_d[v] == INF || max_d[v] < dist[v])
max_d[v] = dist[v] ;
if (!used[v])
{
q.push (v) ;
used[v] = 1 ;
}
}
}
}
}
int main ()
{
int i, j ;
int u, v, w ;
int tcase, mz, minV, id ;
while (scanf ("%d", &tcase) != EOF)
{
while (tcase--)
{
MEM (first, -1) ;
MEM (max_d, INF) ;
edgeCnt = 0 ;
scanf ("%d%d", &nz, &nr) ;
for (i = 0 ; i < nz ; ++i)
{
scanf ("%d%d", &u, &mz) ;
while (mz--)
{
scanf ("%d", &v) ;
add (v, u, 1) ;
add (u, v, 1) ;
}
}
while (nr--)
{
scanf ("%d", &v) ;
for (i = 0 ; i < v ; ++i)
{
scanf ("%d", &u) ;
spfa (u) ;
}
}
minV = INF ;
id = -1 ;
for (i = 0 ; i < MAXN ; ++i)
if (max_d[i] != INF)
{
if (minV == INF || minV > max_d[i])
{
minV = max_d[i] ;
id = i ;
}
}
printf ("%d %d\n", minV, id) ;
}
}
return 0 ;
}
分享到:
相关推荐
最短路课件(链式前向星+堆优化+SPFA)
蓝桥杯CJ2-11-图论最短路径问题 Bellman-Ford算法+SPFA.pdf
强大的SPFA,非常强大。 写的很不错 , 大家都下来看看吧
SPFA入门,很好的入门指南。值得一下!
各种算法资料介绍和代码事例(包括2-Sat,A*,SPFA,BFS,DFS,DBFS,Dancing Links,BM,Dijkstra,Dinic,Floyd,Gabow,KMP,Prim,MD5,SAP,RMQ,Tarjan,ST,匈牙利算法,朱刘算法等),还有很多算法,不一一列出,列出这么多,是想...
使用C++实现的Queue improved Bellman-Ford单源最短路算法,在国内还被叫做SPFA。这个程序输入一个图,找到图中的一个点,这个点到最远点的长度最短。图使用邻接表保存。
最短路SPFA算法。SPFA(Shortest Path Faster Algorithm)算法是求单源最短路径的一种算法,它是Bellman-ford的队列优化,它是一种十分高效的最短路算法。存在负权边时使用。
这里面的内容是个PPT,介绍的很好,如果你想更加的清楚 SPFA 和Bellman_ford.ppt 最短路算法的原理,这是个不错的选择
最短路之SPFA算法.rar。。。算法复分析及例题设计,综合分析
SPFA——Shortest Path Faster Algorithm,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。
做ACM最短路问题普遍算法的Floyd-Dijkstra-Spfa板子..
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 这个是自己写的,思想还是一样发的。
该PPT讲了求最短路算法SPFA,Bellman-Ford和Floyed-Warshall算法,还拓展了差分约束。十分适合初学者用
图论- 最短路- Bellman-Ford 算法与 SPFA.rar
最短路全家桶(Floyd,Dijkstra,SPFA)量大管饱
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 SPFA算法是西南交通大学段凡丁于1994年发表的. 从名字我们就可以看出,这种算法在效率上一定有过人之处。 很多时候,给定的图存在负权边,这时...
求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 从名字我们就可以看出,这种算法在效率上一定有过人之处。
摘要:VC/C++源码,算法相关,队列优化,最短路径算法 C++队列优化的Bellmanford最短路算法(SPFA),使用C++实现的Queue improved Bellman-Ford单源最短路算法,在国内还被叫做SPFA。这个程序输入一个图,找到图中的一...
最短路无向图spfa+slm优化,可作为模板使用
基本思想 用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。...d[i]:起点s到i的临时最短路长度 松驰的结果是使j的d值减小