Telephone Lines

可以设计出dp[x,p]表示从1号节点到达x号节点，指定p条边免费时，经过的路径上最贵的边的最小花费是多少。对于一条边(x,y,z)，用max(dp[x,p],z)更新dp[y,p]的值，用dp[x,p]更新dp[y,p+1]的值。但是由于给出的是一张无向图，已经推导出的状态可能会由后续状态再次更新（没有一个确定的顺序更新dp方程）。考虑利用迭代思想，不断利用变量当前的旧值推出新值，借助SPFA算法进行动态规划，直到所有状态都被更新完。

从最短路问题的角度去理解，图中的节点可以扩展到二维，用(x,p)代表一个节点（dp方程的一个状态），从(x,p)到(y,p)连一条长度为z的边，从(x,p)到(y,p+1)连一条长度为0的边。D[x,p]表示从起点(1,0)到节点(x,p)路径上最长的边最短是多少。

从(x,p)这个节点走到(y,p)这个节点，z有可能更新答案，所以连一条长度为z的边。

从(x,p)这个节点走到(y,p+1)这个节点，答案是由(x,p)更新的，所以连一条长度为0的边。

每次从x节点选择走不同的路到y节点，都对应着dp方程的一个状态转移。

而要求的就是所有状态转移出来的最终状态的最小值，最短路跑出来的就是从(1,0)到(x,p)所有路径上边的最小值。最终的答案也是一样的。

\(\\\)

最优贸易

从节点\(1\)开始跑SPFA，首先求出节点\(1\)到节点\(x\)的所有路径中，能够经过的权值最小的节点的权值。

建立反图，从节点\(n\)开始跑SPFA，求出节点\(n\)到节点\(x\)（正图上的节点\(x\)到节点\(n\)）的所有路径中，能够经过的权值最大的节点的权值。

\(\\\)

Roads and Planes G

有边权为负数的边，不能跑\(\text{Dijkstra}\)，据说它又卡SPFA。

观察到双向边的边权为非负，且可能形成环，考虑把每个连通块看成一个“点”，再把有向边加到图内，就得到一张有向无环图。在有向无环图上，无论边权正负，都可以按照拓扑序进行扫描，在线性时间内求出单源最短路，可以利用拓扑序的框架处理整个图。在每个连通块内跑dijkstra，实际上在块内跑Dijkstra时顺便完成了块之间的转移。

这样并不是相当于Dijkstra跑了负边。在一个块内跑Dijkstra时，如果进行的是块之间的转移，那么另一个块的点并不会进入当前块进行Dijkstra的优先队列中。所以Dijkstra实际上并没有跑负边。只是相当于普通的拓扑图上的扫描转移。

因为有边权为负的边存在，所以当无解的时候不一定就dis\(\ge\) INF，比较好的判断方法是在跑Dijkstra时，访问到这个\(x\)点时，如果dis[x]==INF，肯定是没有办法到达的。

一开始把一个连通块上所有的点都放进了堆里，如果一个点出堆的时候的dis为INF，肯定是最后才出队的，所有连通块里能更新的点应该都更新了，还是没更新它，一定说明它是不能到达的。

换到其它的最短路上，一个点都是被其它点能更新的时候才会进堆。如果它的dis是INF，说明它没进过堆，一定是不能被到达的。

\(\\\)

最短路计数

由于图上的边权都是1，考虑用bfs代替SPFA，Dijsktra之类的。自环可以删除，重边可以被算作不同的路径，照样存储。第一次访问到时，记录路径长度，答案加上它父节点的答案。后面访问到这个点，如果是最短路的话，直接加上它父节点的答案。

\(\\\)

通往奥格瑞玛的道路

二分答案加最短路判定。

\(\\\)

牛的旅行 Cow Tours

一开始读错题了，上来就想到了暴力加边删边跑最长路。后来发现是求所有点对之间最短路的最大值的最小值。最长路跑出来的不是最短路的最大值。

首先dfs标记连通块，floyd求出任意两点间的最短路，求出连通块的直径，再求出在不同牧场两点间连一条边后的直径。三者取最大值后，就是当前的答案。在所有的答案中取最小值。

\(\\\)

速度限制

一开始想到了，用所有与它相连的边的速度替代没有速度限制的边的速度，然后连出所有的边后，跑最短路。

越测越不对…甚至还发了求助帖，原因在于最短路上跑到没有速度限制的边的时候可能用的是\(v\)速度的边，但是更新这条没有速度限制的边用的是\(u\)速度的边。并不符合按照原来的速度行驶。

看了题解后发现是二维的dijkstra（并不太好理解为分层图最短路），用\(dis[i][j]\)表示以\(j\)的速度到达\(i\)点时的最短路径。用\(「x,lstv」\)更新\(「y,now」\)时，如果\(nowv==0\)，那么用\(lstv\)更新。如果有限速标志用\(nowv\)更新。