正文
HDU6331 Problem M. Walking Plan【Floyd + 矩阵 + 分块】
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
HDU6331 Problem M. Walking Plan
题意：
给出一张有\(N\)个点的有向图，有\(q\)次询问，每次询问从\(s\)到\(t\)且最少走\(k\)条边的最短路径是多少
\(N\le 50, q\le 10^5, k\le 10^4\)
题解：
如果暴力预处理的话复杂度是\(kN^3\)也就是\(1.25\times 10^9\)，空间上肯定开不起
第二个想法就是对邻接矩阵进行矩阵快速幂，对于每次询问都要跑一次，复杂度是\(qN^3\log k\)复杂度更高了
考虑分摊复杂度，\(k\)最多是\(10^4\)，那么可以每\(\lfloor\sqrt{k}\rfloor\)的长度跑一次最短路，跑\(\lceil\frac{k}{\lfloor\sqrt{k}\rfloor}\rceil\)次，最后计算的时候询问\(k\)可以把\(k\)拆成\(l\times \sqrt{k} + r\)，然后用两个对应的最短路矩阵再找一次最短路即可，要注意的是，最短路不一定是单调的，也就是说可能走更多的边可以得到更短的路径，但是多走的边不会超过\(N\)，因为两点之间的最短路长度是不会超过顶点数的，所以预处理时需要计算的是\(u\)到\(v\)走了至少\(k\)步的最短路，最后的复杂度是\(\sqrt{k}N^3+qN\)大概是\(2\times 10^7\)
view code
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 55;
const int INF = 0x3f3f3f3f;
int n, m;
struct Matrix{
int A[MAXN][MAXN];
Matrix(){ for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) A[i][j] = INF; }
void clear(){ for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) A[i][j] = INF; }
Matrix operator * (const Matrix &rhs) const{
Matrix ret;
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
ret.A[i][j] = min(ret.A[i][j],A[i][k] + rhs.A[k][j]);
return ret;
}
};
Matrix dis1[155], dis100[111];
void solve(){
scanf("%d %d",&n,&m);
dis1[1].clear();
for(int i = 1; i <= m; i++){
int u, v, w;
scanf("%d %d %d",&u,&v,&w);
dis1[1].A[u][v] = min(dis1[1].A[u][v],w);
}
for(int i = 2; i <= 150; i++) dis1[i] = dis1[i-1] * dis1[1];
dis100[1] = dis1[100];
for(int i = 2; i <= 100; i++) dis100[i] = dis100[i-1] * dis100[1];
for(int i = 149; i >= 1; i--)
for(int u = 1; u <= n; u++)
for(int v = 1; v <= n; v++)
dis1[i].A[u][v] = min(dis1[i].A[u][v],dis1[i+1].A[u][v]);
int q;
scanf("%d",&q);
while(q--){
int s, t ,k;
scanf("%d %d %d",&s,&t,&k);
int ret = INF;
if(k<=100) ret = dis1[k].A[s][t];
else{
int l = (k-1) / 100, r = k - l * 100;
for(int i = 1; i <= n; i++) ret = min(ret,dis100[l].A[s][i] + dis1[r].A[i][t]);
}
printf("%d\n",ret==INF?-1:ret);
}
}
int main(){
int tt;
for(scanf("%d",&tt); tt; tt--) solve();
return 0;
}
