最短路径 – Tgotp-Blog

最短路(route)

先套路的正反求两次最短路,然后容易发现如果反向能更新最短路直接输出1

然后如果不变或者如果这条边压根不在最短路上则输出0,

如果均不是,接下来就是判断这条路是否在最短路上必须经过.

(评讲的时候大佬们给了很多做法,[......]

Read more

2118: 墨墨的等式

考虑如果现在需要放最后一个位置的值,前面和为X

那么就有 B = X + k * an

即如果限制了X,就可以通过枚举k来得到B的取值

显然可以有 B = X % an + k * an

容易发现 X  < an,那么令an = min(ai)

那么就可以通过X来[......]

Read more

NOIP2014D2T2 P2296 寻找道路

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

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

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

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

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

Read more

BZOJ1073: [SCOI2007]kshort

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

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

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

Read more

玛丽卡

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