2018HDU多校训练-3-Problem M. Walking Plan

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6331

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Walking Plan

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

Source

2018 Multi-University Training Contest 3

Recommend

chendu

这题时间复杂度卡的。。。。

题解：这题主要用来分块+DP+Folyd.对于数据范围，我们分100位每一块（一般大一点，我取110 Orz）.我们可以先预处理出任意两点间走从0~110步的最短路，然后利用走100为一个单位步，

去更新1*100,2*100,....100*100步的最短路，

由于是至少为K条路的最短路，因此>=k. 我们可以可以再预处理更新一遍恰好走x*100步的情况，查找还有没有于x*100的情况使得i->j的距离变小（因为最多50个点，所以不会超过100）我们把K 分为K/100,,和K%100,分别求；

参考代码为：

 #include<bits/stdc++.h>

 using namespace std;

 const int INF=0x3f3f3f3f;

 const int N=,M=,maxn=;

 int T,n,m,q,u,v,w,s,t,K;

 int a[maxn][N][N],b[maxn][N][N],Map[N][N];

 int flag[N][N],dis[N][N];

 void pre_work(int x[N][N],int y[N][N],int z[N][N])

 {

     for(int i=;i<n;i++)

     {

         for(int j=;j<n;j++)

         {

             flag[i][j]=INF;

             for(int k=;k<n;k++)

                 flag[i][j]=min(flag[i][j],x[i][k]+y[k][j]);

         }

     }

     for(int i=;i<n;i++)

         for(int j=;j<n;j++) z[i][j]=flag[i][j];

 }

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie();

     cin>>T;

     while(T--)

     {

         cin>>n>>m;

         for(int i=;i<n;i++)

         {

             for(int j=;j<n;j++) Map[i][j]=INF;

         }

         while(m--)

         {

             cin>>u>>v>>w;

             Map[u-][v-]=min(Map[u-][v-],w);

         }

         for(int i=;i<n;i++)

         {

             for(int j=;j<n;j++)

                 a[][i][j]=b[][i][j]= i==j? :INF;

         }

         for(int i=;i<M;i++) pre_work(a[i-],Map,a[i]);//处理出经过i步从 x->y 的最短路

         for(int i=;i<M;i++) pre_work(b[i-],a[],b[i]);//处理出从 x->y 恰好走  100*i步

         //Floyd

         for(int i=;i<n;i++)

         {

             for(int j=;j<n;j++) dis[i][j]= i==j? :Map[i][j];

         }

         for(int k=;k<n;k++)

         {

             for(int i=;i<n;i++)

             {

                 for(int j=;j<n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

             }

         }

         for(int x=;x<M;x++)

         {

             for(int i=;i<n;i++)

             {

                 for(int j=;j<n;j++)

                 {

                     flag[i][j]=INF;

                     for(int k=;k<n;k++) flag[i][j]=min(flag[i][j],b[x][i][k]+dis[k][j]);

                 }

             }

             for(int i=;i<n;i++) for(int j=;j<n;j++) b[x][i][j]=flag[i][j];

         }

         cin>>q;

         while(q--)

         {

             cin>>s>>t>>K; s--,t--;

             int r=K/,l=K%,ans=INF;

             for(int i=;i<n;i++) ans=min(ans,b[r][s][i]+a[l][i][t]);

             if(ans>=INF) cout<<-<<endl;

             else cout<<ans<<endl;

         }

     }

     return ;

 }

巴特西

2018HDU多校训练-3-Problem M. Walking Plan

最新文章

热门文章