2012-0054
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[大意]求最少的点数覆盖所有1到n的最短路径
[做法]最短路+网络流
先求出最短路， 用spfa或者dijstra+heap都可以，满足dist[v] = dist[u] + edge[u][v]的边<u,v>也会是最短路图上面的边。 注意如果1到n的最短路存在有<1,n>, 就无解-1。
若不是，那么新建一个图，除了1和n，其他点都拆点, 分成入点和出点, 用容量为1的边连接自己的入点到出点；最短路上面的边<u,v>, 变成用容量为无限大的边连接u的出点到v的入点。 新图的最小割即是题目所求, 用dinic来求最大流。
by FJYsmall[大意]求最少的点数覆盖所有1到n的最短路径
[做法]最短路+网络流
先求出最短路， 用spfa或者dijstra+heap都可以，满足dist[v] = dist[u] + edge[u][v]的边
若不是，那么新建一个图，除了1和n，其他点都拆点, 分成入点和出点, 用容量为1的边连接自己的入点到出点；最短路上面的边
by FJYsmall