GJOI 2023.10.5 T2 假期计划Ⅱ
题意：给出一个有 \(n\) 个点的有向图，每点到另一点都有一条有向边，边有权值。现有 \(n^2\) 次操作，每次会删去一些边，问每次删去后从 \(1\) 号点到 \(n\) 号点经过恰好 \(k\) 条边的最短路，若无法到达输出 \(-1\)。
\(n \le 300 , k \le 8\)
输入：
3 4
10 4 4
9 5 3
2 1 6
3 1
2 3
2 1
3 2
2 2
1 3
3 3
1 1
1 2
输出：
11
18
22
22
22
-1
-1
-1
-1
这道题有人说可以暴力 \(SPFA\) 过，这里讲一下我的思路。
由于求最短路，再加上 \(k\) 很小，我们可以考虑折半。
考虑 \(f_{i,j}\) 为 \(1\) 经过 \(i\) 条边到 \(j\) 的最短路，\(d_{i,j}\) 则为 \(j\) 经过 \(i\) 条边到 \(n\) 的最短路，这里 \(1 \le i \le 4\)。
那么最后答案就是 \(min(f_{k/2,i}+d_{k-k/2,i})\) , \(1\le i\le n\)
那如何去求 \(f\) 与 \(g\) 数组呢？
我们可以加一个数组 \(v_{i,j,u}\) ，表示 \(j\) 经过 \(i\) 条边 到 \(u\) 的最短路，这里 \(1 \le i \le 2\)。
那么逆向思维，从所有边都删完开始，每次加进一条边，看会对原图产生什么影响。
设此边从 \(x\) 到 \(y\) 。
首先维护好 \(v\) 数组，\(i=1\) 时赋值，\(i=2\) 时就考虑一个节点经过 \(x\) 到 \(y\) ，或从 \(x\) 出发到 \(y\) 到一个节点的最短路，复杂度 \(O(n)\)。
接下来就来看 \(f\) 与 \(g\) 数组的维护。
\(i=1,i=2\) 时直接用 \(v\) 赋值，复杂度 \(O(n)\)。
\(i=3\) 或 \(i=4\) 时分情况讨论。
若此边为路径上的第一条边，那么就是枚举两个节点 \(i,j\) ，从 \(x\) 到 \(y\) 再经过 \(1\) 条边到 \(i\) 再经过 \(1/2\) 条边到 \(j\) ，复杂度 \(O(n^2)\)，但由于只会做 \(n\) 次，不会影响总复杂度。
若是第二条边或第三条边，那么只是枚举从起点到 \(x\) 再到 \(y\) 再到目标节点，复杂度 \(O(n)\)。
若是第四条边，那么只是从 \(1/n\) 出发经过 \(3\) 条边到 \(x\) 再到 \(y\) 的最短路，复杂度 \(O(n)\)。
最后求解答案即可。
时间复杂度 \(O(n^3)\)
Code
#include<bits/stdc++.h>
#define min(a,b) (a<b?a:b)
using namespace std;
struct datay
{
int x,y;
}l[100005];
int n,m,a[305][305],f[5][305],d[5][305],t[100005],v[3][305][305];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);
}
for(int i=1;i<=n;i++)f[1][i]=f[2][i]=f[3][i]=f[4][i]=1e9+5;
for(int i=1;i<=n;i++)d[1][i]=d[2][i]=d[3][i]=d[4][i]=1e9+5;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)v[1][i][j]=v[2][i][j]=1e9+5;
}
for(int i=1;i<=n*n+2;i++)t[i]=1e9+5;
for(int i=1;i<=n*n;i++)
{
scanf("%d%d",&l[i].x,&l[i].y);
}
int x,y;
for(int u=n*n;u>=1;u--)
{
x=l[u].x;
y=l[u].y;
t[u]=t[u+1];
v[1][x][y]=a[x][y];
for(int i=1;i<=n;i++)
{
v[2][i][y]=min(v[2][i][y],v[1][i][x]+a[x][y]);
v[2][x][i]=min(v[2][x][i],a[x][y]+v[1][y][i]);
}//维护 v 数组
for(int i=1;i<=n;i++)
{
f[1][i]=min(v[1][1][i],f[1][i]);
d[1][i]=min(v[1][i][n],d[1][i]);
f[2][i]=min(v[2][1][i],f[2][i]);
d[2][i]=min(v[2][i][n],d[2][i]);
}//维护 i=1,2 时的 f 与 d 数组
if(x==1)
{
for(int i=1;i<=n;i++)f[3][i]=min(f[3][i],a[x][y]+v[2][y][i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[4][j]=min(f[4][j],a[x][y]+v[1][y][i]+v[2][i][j]);
}
}
}
if(y==n)
{
for(int i=1;i<=n;i++)d[3][i]=min(d[3][i],a[x][y]+v[2][i][x]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
d[4][j]=min(d[4][j],v[2][j][i]+v[1][i][x]+a[x][y]);
}
}
}//维护第1条边的情况
for(int i=1;i<=n;i++)
{
f[3][i]=min(f[3][i],v[1][1][x]+a[x][y]+v[1][y][i]);
d[3][i]=min(d[3][i],v[1][i][x]+a[x][y]+v[1][y][n]);
if(y==i)f[3][i]=min(f[3][i],v[2][1][x]+a[x][y]);
if(x==i)d[3][i]=min(d[3][i],a[x][y]+v[2][y][n]);
}//i=3的其他情况
for(int i=1;i<=n;i++)
{
f[4][i]=min(f[4][i],v[1][1][x]+a[x][y]+v[2][y][i]);
d[4][i]=min(d[4][i],v[2][i][x]+a[x][y]+v[1][y][n]);
f[4][i]=min(f[4][i],v[2][1][x]+a[x][y]+v[1][y][i]);
d[4][i]=min(d[4][i],v[1][i][x]+a[x][y]+v[2][y][n]);
if(y==i)f[4][i]=min(f[4][i],f[3][x]+a[x][y]);
if(x==i)d[4][i]=min(d[4][i],a[x][y]+d[3][y]);
}//i=4的其他情况
for(int i=1;i<=n;i++)t[u]=min(t[u],f[m/2][i]+d[m-m/2][i]);
}
for(int i=1;i<=n*n;i++)printf("%d\n",t[i+1]>1e9?-1:t[i+1]);
return 0;
}