hdu6331 /// Floyd+分块DP

题目大意：

给定单向图的n m 为点数和单向边数

接下来m行给定 u v w 为边的起点终点和长度

给定q 为询问个数

接下来q行给定 x y k 求从x到y至少经过k条边的最短路长度

https://blog.csdn.net/qkoqhh/article/details/81301910

设 d[ i ][ j ][ k ] 为从i到j走至少k条边的最短路长度

设 f[ i ][ j ][ k ] 为从i到j恰好走k*100条边的最短路长度

那么至少走K条边的话

若 K>=100 有 f[ i ][ j ][ K/100 ] + d[ i ][ j ][ K%100 ]

若 K%100==0 有 f[ i ][ j ][ K/100 ]

若 K<100 有 d[ i ][ j ][ K ]

最小值就是至少走K条边的最短路

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define inc(i,l,r) for(int i=l;i<=r;i++)

#define dec(i,r,l) for(int i=r;i>=l;i--)

const int N=+;

const int M=1e4+;

int n, m;

int d[N][N][], f[N][N][];

int main()

{

    int _; scanf("%d",&_);

    while(_--) {

        scanf("%d%d",&n,&m);

        inc(i,,n)inc(j,,n) d[i][j][]=INF;

        while(m--) {

            int u,v,w; scanf("%d%d%d",&u,&v,&w);

            d[u][v][]=min(d[u][v][],w); // 更新至少1条边的答案

        }

        inc(i,,n)inc(j,,n) d[i][j][]=d[i][j][];

// 至少0条边的答案应和至少1条相同

        inc(i,,n) d[i][i][]=;

// 点到本身的距离至少0条边答案肯定为0

        inc(k,,) {

            inc(i,,n)inc(j,,n) d[i][j][k]=INF;

            inc(p,,n)inc(i,,n)inc(j,,n) // Floyd

                d[i][j][k]=min(d[i][j][k],d[i][p][k-]+d[p][j][]);

        }

        inc(i,,n)inc(j,,n) f[i][j][]=d[i][j][];

// 按100条边（求了150条）分块应该够了

        inc(k,,) {

            inc(i,,n)inc(j,,n) f[i][j][k]=INF;

            inc(p,,n)inc(i,,n)inc(j,,n) // Floyd

                f[i][j][k]=min(f[i][j][k],f[i][p][k-]+f[p][j][]);

        }

        dec(k,,)

            inc(i,,n)inc(j,,n)

                d[i][j][k]=min(d[i][j][k],d[i][j][k+]);

// 至少k条边的答案 如果k+1的答案更优 同样可以更新

        int q; scanf("%d",&q);

        while(q--) {

            int u,v,k; scanf("%d%d%d",&u,&v,&k);

            int ans=INF;

            if(k>) {

                inc(p,,n)

                ans=min(ans,f[u][p][k/]+d[p][v][k%]);

            }

            if(k%==) ans=min(ans,f[u][v][k/]);

            if(k<=) ans=min(ans,d[u][v][k]);

            if(ans==INF) printf("-1\n");

            else printf("%d\n",ans);

        }

    }

    return ;

}