Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
我觉得这题题意不是那么清楚这个题是找有没有一条权值为负的回路,用SPFA是OK的,但是如果任意选择一点搜到其他点的最短时间,入队列大于n次就证明存在负权值回路这样做是不是有BUG,假如这个图不是连通的,而你从一个孤立点开始查找,这样也许会是错的吧,题目中并没有说明这图一定是连通的,是不是要我这么想 ,在现实生活中农场的各个地方一定是连通的啊。。。。。 但是我只从1开始判断,结果也是正确的,只证明测试数据弱吧 我的想法是由于虫洞只有50个,从每个虫洞的起始点开始搜,应该不会漏算答案 然后希望用邻接表存,邻接矩阵存了的话,复杂度提高了,顶点有500个,边只有2500+200条,算稀疏图了吧 如果一定要用邻接矩阵存的话,注意一下重边的情形,选择时间花费最少的应该总是正确答案 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator