bzoj 1003: [ZJOI2006]物流运输 spfa+dp

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=1003


由于n和m都很小,所以我们可以预处理出w[i][j]:表示第i天到第j天中,1到n的最短路

然后再小小的dp一下:

dp[i]=w[1][i]*i

dp[i]=min(dp[i] , dp[j]+k+w[j+1][i]*(i-j) )  (j<i)

ans=dp[n]

2018年6月21日 更新:感谢Michael_Bryant提醒我代码放错了…

发表评论