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;

}

巴特西

HDU6331 Problem M. Walking Plan【Floyd + 矩阵 + 分块】

题意：

题解：

最新文章

热门文章