最短路及其衍生讲解
注意dij堆优化要在\(int u=q.top().seond\)下面写\(if(vis[u])continue;\)和\(vis[u]=1\),因为这是代表\(u\)此时放进与起点同一集合了。
判负环
spfa做，十分简单，记录一个点入队次数或到某个点路径长度,\(>=n\)即有负环，模板
建反图
其实就是当我们有多个起点，但只有一个终点时，反向建边，以原终点为起点跑最短路。
（eg：最优贸易），当我们需要进行记录两个值时（比如题中的买入和卖出），可正反各跑一遍，然后用1 ~ u和n ~ u的答案求。
分层图最短路
名字挺高级，事实上不是啥难东西\(QWQ\)，其实就是我们正常为\(dis[u]\)现在变为\(dis[k][u]\),多增加一维表示其他量的状态，一个\(k\)层的分层图上的\(u\),就相当于一个二元组\((k,u)\)。
(eg:汽车加油)