题解 CF793D 【Presents in Bankopolis】
xzggzh1
·
·
题解
题意：
一个有向图，节点有编号，找一条经过 k 个点的最短路径，要求是当前边不能跃过已经经过的节点。即对于路径中的边 x \to y ，不存在以前经过的点 t 使得 x <t<y 。
---
每一次经过一条边都会使得可以到达的边的范围缩小。
考虑到 $ 1 \leq n,k \leq 80 $ 我们不难想到直接把可以去的区间存下来做$\rm DP$，
再按照类似区间$\rm DP$的做法开一维 $0,1$ 表示当前到达的端点是左端点还是右端点，然后直接转移即可。
具体的说，我们可以设 $f[i][j][k][0/1]$ 表示经过 $i$ 个点，可以去的区间是 $[j,k]$ ，现在在 左端点/右端点。其中第一维可以用滚动数组存。
---
剩下的一些小细节可以看代码：
```cpp
const int N=85;
int n,K,m,u,v,c,cc[N][N],f[2][N][N][2],i,j,k,nw,ans=1<<30;
int main(){
memset(cc,1,sizeof cc);
scanf("%d%d%d",&n,&K,&m);
while(m--)scanf("%d%d%d",&u,&v,&c),cc[u][v]=min(cc[u][v],c);
memset(f[0],1,sizeof f[0]);
for(i=1;i<=n;++i)f[0][0][i][1]=f[0][i][n+1][0]=0;
while(--K){
nw^=1;memset(f[nw],1,sizeof f[nw]);
for(i=0;i<=n-1;++i)for(j=i+2;j<=n+1;++j)for(k=i+1;k<j;++k){
f[nw][i][k][1]=min(f[nw][i][k][1],min(f[!nw][i][j][1]+cc[j][k],f[!nw][i][j][0]+cc[i][k]));
f[nw][k][j][0]=min(f[nw][k][j][0],min(f[!nw][i][j][0]+cc[i][k],f[!nw][i][j][1]+cc[j][k]));
}
}
for(i=0;i<=n+1;++i)for(j=0;j<=n+1;++j)ans=min(ans,min(f[nw][i][j][0],f[nw][i][j][1]));
if(ans>1<<20)ans=-1;
printf("%d\n",ans);
}
```