P2939 [USACO09FEB]改造路Revamping Trails


同bzoj2763。不过dbzoj太慢了,bzoj又交不了。

裸的分层图最短路。

f[i][j]表示免费走了j条路到达i的最短代价。

f[i][j]->f[k][j+w(i,k)](i和k之间的边代价为w(i,k))

f[i][j]->f[k][j+1](i和k之间有边)

然后每个f都建一个点。

懒得贴了

05-08 08:30