[BZOJ1579] [Usaco2009 Feb]Revamping Trails 道路升级（分层图最短路 + 堆优化dijk）传送门

dis[i][j]表示第i个点，更新了j次的最短路
此题不良心，卡spfa


#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 50001

usi

[BZOJ1576] [Usaco2009 Jan]安全路经Travel（堆优化dijk + （并查集 || 树剖））传送门

蒟蒻我原本还想着跑两边spfa，发现不行，就gg了。
首先这道题卡spfa，所以需要用堆优化的dijkstra求出最短路径
因为题目中说了，保证最短路径有且只有一条，所以可以通过dfs

[luoguP1783] 海滩防御（二分 || 最短路 || 最小生成树）传送门

因为答案满足单调性，所以看到这个题，第一反应是二分，但是总是WA，也没有超时。

看了题解，，，，，，

这题刚开始很多人会想到二分，二分答案，然后看看是否能绕过所有信号塔，但是，这样

[POJ3463] Sightseeing（次短路 Heap + Dijkstra）传送门

用dijkstra比较好，spfa可能有的重复
dis[x][2]:dis[x][0]表示起点到x的最短路、dis[x][1]表示起点到x的次短路；
tot[x][2]:tot[x][0]表示起点到x的最短路条数、tot[x

【模板】Dijkstra的heap优化为了将最小费用最大流的spfa优化，决定将spfa换成heap优化的Dijkstra。（dijkstra不能处理负边权）
所以还得现学。。。
白点表示已经确定最短路径的点。
蓝点表示还未确定最短路