- 混淆 n 和 m,n 是天数,m 是点数,检查你计算 cost[i][r] 时,枚举的是不是点数 m,还有 cost[i][j]=d[m]。
for(int i=1; i<=n; i++)
{
for(int j=i; j<=n; j++)
{
memset(ok, 0, sizeof ok);
for(int u=1; u<=m; u++)
for(int k=i; k<=j; k++)
if(limit[k][u])
...
spfa(1);
cost[i][j] = d[m];
}
}
- 容易爆 int 的地方:题中说每天都会有一条从 1~m 的路线,但是不保证第 i~j 天走同一条路能够到达,所以 cost[i][j] 可能会等于 INF,所以和 (i−j) 相乘就会爆掉,所以你可以采取下面这种写法来保证不会爆 int:
for(int i=1; i<=n; i++)
{
f[i] = 2e9;
for(int j=0; j<i; j++)
{
if(cost[j+1][i]!=INF)
f[i] = min(f[i], f[j] + cost[j+1][i] * (i - j) + (!!j) * k);
}
}
关于为什么要 (!!j) * k,如果不这样的话,从 j=0 转移的话就会多加上 k。