spfa – Tgotp-Blog

1880: [Sdoi2009]Elaxia的路线

坑了我一晚上的题

太坑了,竟然是solve的vis的毛病

跑四遍spfa,找找最长链,搞定

ps:貌似这道题这样是错的,但是数据很水,所以。。。但是我不想改了233

c++代码如下:

 

BZOJ1073: [SCOI2007]kshort

自己做了一遍卡在字典序小的优先这里,然后理解了不想再打。。。。就复制了

求图的s-t第K短简单路问题,若有长度相同的,字典序小的优先。

首先,由于是简单路,所以A*是不能做的,因为有可能有两条s-i(i为某个中间点)路P1和P2,P1比P2短,但由于P1到达的顶点与P2不同,导致最终沿P[......]

Read more