Problem M. Walking Plan
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 897 Accepted Submission(s): 328
Problem Description
There are n intersections in Bytetown, connected with m one way streets. Little Q likes sport walking very much, he plans to walk for q days. On the i-th day, Little Q plans to start walking at the si-th intersection, walk through at least ki streets and finally return to the ti-th intersection.
Little Q's smart phone will record his walking route. Compared to stay healthy, Little Q cares the statistics more. So he wants to minimize the total walking length of each day. Please write a program to help him find the best route.
Input
The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.
In each test case, there are 2 integers n,m(2≤n≤50,1≤m≤10000) in the first line, denoting the number of intersections and one way streets.
In the next m lines, each line contains 3 integers ui,vi,wi(1≤ui,vi≤n,ui≠vi,1≤wi≤10000), denoting a one way street from the intersection ui to vi, and the length of it is wi.
Then in the next line, there is an integer q(1≤q≤100000), denoting the number of days.
In the next q lines, each line contains 3 integers si,ti,ki(1≤si,ti≤n,1≤ki≤10000), describing the walking plan.
Output
For each walking plan, print a single line containing an integer, denoting the minimum total walking length. If there is no solution, please print -1.
Sample Input
2
3 3
1 2 1
2 3 10
3 1 100
3
1 1 1
1 2 1
1 3 1
2 1
1 2 1
1
2 1 1
Sample Output
111
1
11
-1
题目大意：给出n个点和m条边，给出边的关系，解决q次询问，每次询问是问u点到v点至少走k条边的最短路
仔细想一想觉得很巧妙，我们可以设几个dp数组，dp[k][i][j]表示恰好走k条边从i点走到j点，这样跑一百遍，就可以得出恰好走100条边从i点走到j点，询问中的边的个数是10000的，所以就分成组，我们用dp1数组来存，dp1[k][i][j]就表示走100k条边从i点到j点，处理完这个，再用最开始存边的邻接矩阵跑一个floyd，为什么要跑floyd呢，因为在前面我们走的是恰好k条边，如果在前面就跑floyd，那么会不知道到底走了多少条边，而题目问的是至少，所有假如要101条边，那么我们已经处理了100条边的情况，剩下的就是至少一条边了，而用floyd怎样跑出的最短路都会大于一条。（也不知道理解的对不对）
按照dls的解释，分块的作用在于可以每次转移100次，而不用管中间的点 emmmm。。。。。。
剩下的k%100条边我是处理的每个点之间正好走（0-150）条边的最短路，然后每一个去上一个的最小值，多取50条边是因为最多就50个点
Code：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=60;
const int inf=0x3f3f3f3f;
int map[maxn][maxn];
int dp[110][maxn][maxn];
int dp1[110][maxn][maxn];
int dp3[170][maxn][maxn];
int main()
{
int test;
scanf("%d",&test);
while(test--)
{
memset(map,inf,sizeof(map));
memset(dp,inf,sizeof(dp));
memset(dp1,inf,sizeof(dp1));
memset(dp2,inf,sizeof(dp2));
int n,m;
scanf("%d%d",&n,&m);
for(int i=0; i<m; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
map[u][v]=min(map[u][v],w);
}
for(int i=1; i<=n; i++)
{
dp[0][i][i]=0;
}
for(int k=1; k<=100; k++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
for(int a=1; a<=n; a++)
{
dp[k][i][j]=min(dp[k][i][j],dp[k-1][i][a]+map[a][j]);
}
}
}
}
memset(dp3,0x3f,sizeof dp3);
#define rep(i,a,b) for(int i=a;i<=b;i++)
rep(i,1,n)dp3[0][i][i]=0;
rep(k,1,148)
{
rep(i,1,n)
{
rep(j,1,n)
{
rep(u,1,n)
{
dp3[k][i][u]=min(dp3[k][i][u],
dp3[k-1][i][j]+map[j][u]);
}
}
}
}
for(int k=159; k>=0; k--)
{
rep(i,1,n)
{
rep(j,1,n)
dp3[k][i][j]=min(dp3[k][i][j],dp3[k+1][i][j]);
}
}
for(int i=1; i<=n; i++)
{
dp1[0][i][i]=0;
}
for(int k=1; k<=100; k++)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=n; j++)
{
for(int a=1; a<=n; a++)
{
dp1[k][i][j]=min(dp1[k][i][j],dp1[k-1][i][a]+dp[100][a][j]);
}
}
}
}
int q;
scanf("%d",&q);
while(q--)
{
int a,b,k;
scanf("%d%d%d",&a,&b,&k);
int k1=k/100;
int k2=k%100;
int ans=inf;
for(int i=1; i<=n; i++)
{
ans=min(ans,dp1[k1][a][i]+dp3[k2][i][b]);
}
if(ans==inf) puts("-1");
else printf("%d
",ans);
}
}
return 0;
}
/*
2
3 3
1 2 1
2 3 10
3 1 100
3
1 1 1
1 2 1
1 3 1
2 1
1 2 1
1
2 1 1
*/