Codeforces 238E: Meeting Her
1. 题目大意
有一个\(n\)个结点的有向图，边权均为1。Urpal想从\(a\)出发去\(b\)。有\(k\)个公交车公司。在每一秒的开始，第\(i\)个公司的公交车随机选择一条从\(s_i\)到\(t_i\)的最短路径然后走这条路径。如果一个公交车经过Urpal所在的交叉点，则Urpal可以上这辆公交车，他可以在中途任意一个结点下车。
在任何时刻Urpal只知道他自己的位置和约会地点。当他上了公交车时他只知道这辆公交车属于第几个公司。当然Urpal知道城市地图和每个公司的\( (s_i, t_i) \)。
求最坏情况下他需要乘坐公交车的次数。
2. 数据范围
\( 2 \le n \le 100 \)
\( 0 \le k \le 100 \)
\( 0 \le m \le n \cdot (n - 1) \)
保证图中没有自环和重边。
3. 题解
首先在原图上跑floyd，求出两两结点之间的最短路。
设\(f[u]\)为点\(u\)到终点\(b\)最少需要乘坐公交的次数。容易想出一个DP做法，但是这个DP的状态是有环的。对于这种DP，我们一般使用迭代的方法。
每次迭代，我们可以枚举每一条公交线路，对于每一个这条公交线路必然经过的点\(u\)，就可以更新\(f[u]\)的值。具体实现的时候，我们另设一个\(g[u]\)表示乘坐了这条线路的情况下从\(u\)到\(b\)最少需要乘坐公交的次数，那么\(g\)只需简单的记忆化dfs就可以转移。算出\(g\)后，用\(g[u]\)的值更新\(f[u]\)即可。
可以证明迭代的次数一定不超过\(n\)。
4. 时空复杂度
时间复杂度：\( O( n^3k ) \)
空间复杂度：\( O( n^2 ) \)
5. 代码
代码在这里。
