【BZOJ 4152】[AMPPZ2014] The Captain

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4152
神犇题解:http://blog.csdn.net/qq_34731703/article/details/52724766

解题报告

因为横着的边和竖着的边相互独立
于是分开考虑,先考虑横着的边:

直接连是 $ O({n^2})$
但因为 $ dis(i,j) = dis(i,k) + dis(k,j)(i < k < j)$ 所以只连相邻的点就可以啦!

竖着的边也同理
这样的话,边数和点数都是 $ O(n)$ 级别的
于是就可以上正常的最短路辣!
另外,据说这题卡SPFA?

14 thoughts to “【BZOJ 4152】[AMPPZ2014] The Captain”

  1. Aw, this was a very nice post. In idea I wish to put in writing like this moreover – taking time and actual effort to make an excellent article… but what can I say… I procrastinate alot and on no account seem to get one thing done.

  2. 238665 796513Its like you read my mind! You appear to know so a lot about this, like you wrote the book in it or something. I feel which you can do with some pics to drive the message home a bit, but instead of that, this is wonderful weblog. A wonderful read. Ill certainly be back. 253066

  3. 56443 797047Using writers exercises such as chunking. They use numerous websites that contain several creative writing exercises. Writers read an exercise, and do it. 688186

  4. 356739 579223Hello there, just became alert to your blog through Google, and located that it is genuinely informative. Im gonna watch out for brussels. Ill be grateful in case you continue this in future. Several people will be benefited from your writing. Cheers! 17373

Leave a Reply

Your email address will not be published. Required fields are marked *