最短路径 – Tgotp-Blog

NOIP2014D2T2 P2296 寻找道路

脑残少年理解错了一个地方100-10 = 90;

逆向连边然后稠密图筛一下跑最短路用迪杰斯特拉算法。没了。。。

智障筛的时候没区分。。。浪死了,剩下一道明天再做,今天玩游戏玩的有点晚233

目前分数405,刚刚到sc当年的一等线。。。惊惧

c++代码:
[crayon-5a[......]

Read more

BZOJ1073: [SCOI2007]kshort

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

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

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

Read more

玛丽卡

次最短路问题。详情看代码。