【分块】【DP】HDU6331 Walking Plan

题意：

给出n个点，m条边，询问q次，每次求从a到b经过至少k条边的最短路径。

分析：

啊啊啊啊我是傻叉吗。。。。

现场想了个什么5000+5000的分块。。。像个智障一样。。。。

明明可以100*100分块的。。。。

其实看到这应该都知道怎么做了。

定义$DP_a(i,j,k)$表示从i出发，到达j点，并经过刚好$k*100(k\leq 100)$条边的最短路。

定义$DP_b(i,j,k)$表示从i出发，到达j点，并经过刚好$k(k\leq 100)$条边的最短路。

定义$DP_c(i,j,k)$表示从i出发，到达j点，并经过至少$k(k\leq 100)$条边的最短路

求出两个辅助数组$w(i,j)$表示从i到j的边
$dist(i,j)$表示从i到j的最短路

首先最好求的是$DP_b$
$DP_b(i,j,k)=min\{DP_b(i,l,k-1)+w[l][j]\}$

然后有了这个就很好求$DP_a$与$DP_c$了

$DP_a(i,j,k)=min\{DP_a(i,l,k-1)+DP_b(l,j,100)\}$

$DP_c(i,j,k)=min\{DP_b(i,l,k)+dist(l,j)\}$

每次询问时枚举一个中间点$i$

答案就是$min\{ DP_a(u,i,\lfloor\frac k {100}\rfloor)+DP_c(i,v,k\%100)\}$

预处理复杂度$O(100*n*n*n)$询问复杂度$O(q*n)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 55
#define MAXM 110
using namespace std;
int t;
int w[MAXN][MAXN];
int dp[MAXN][MAXN][MAXM],dp1[MAXN][MAXN][MAXM],dp2[MAXN][MAXN][MAXM];
int ans[MAXN];
int dist[MAXN][MAXN];
int min1(int x,int y){if(x==-1)return y;if(y==-1)return x;return min(x,y);
}
int main(){SF("%d",&t);int n,m,q;while(t--){SF("%d%d",&n,&m);memset(w,-1,sizeof w);int u,v,k,val;for(int i=1;i<=m;i++){SF("%d%d%d",&u,&v,&val);w[u][v]=min1(w[u][v],val);}memset(dist,-1,sizeof dist);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)dist[i][j]=w[i][j];dist[i][i]=0;}memset(dp,-1,sizeof dp);for(int i=1;i<=n;i++)dp[i][i][0]=0;for(int k=1;k<=100;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)    for(int l=1;l<=n;l++)if(dp[i][l][k-1]!=-1&&w[l][j]!=-1)dp[i][j][k]=min1(dp[i][j][k],dp[i][l][k-1]+w[l][j]);memset(dp1,-1,sizeof dp1);for(int i=1;i<=n;i++)dp1[i][i][0]=0;for(int k=1;k<=100;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)    for(int l=1;l<=n;l++)if(dp1[i][l][k-1]!=-1&&dp[l][j][100]!=-1)dp1[i][j][k]=min1(dp1[i][j][k],dp1[i][l][k-1]+dp[l][j][100]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)if(dist[j][i]!=-1&&dist[i][k]!=-1)dist[j][k]=min1(dist[j][k],dist[j][i]+dist[i][k]);memset(dp2,-1,sizeof dp2);for(int k=0;k<=100;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int l=1;l<=n;l++)if(dp[i][j][k]!=-1&&dist[j][l]!=-1)dp2[i][l][k]=min1(dp2[i][l][k],dp[i][j][k]+dist[j][l]);SF("%d",&q);for(int i1=1;i1<=q;i1++){SF("%d%d%d",&u,&v,&k);    int tt1=k/100;int tt2=k%100;int ans1=-1;for(int i=1;i<=n;i++)if(dp1[u][i][tt1]!=-1&&dp2[i][v][tt2]!=-1)ans1=min1(ans1,dp1[u][i][tt1]+dp2[i][v][tt2]);PF("%d\n",ans1);}}
}