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

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

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Walking Plan

Problem Description

There are

Input

The first line of the input contains an integer

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,分别求；

参考代码为：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int INF=0x3f3f3f3f;
 4 const int N=55,M=110,maxn=10010;
 5 int T,n,m,q,u,v,w,s,t,K;
 6 int a[maxn][N][N],b[maxn][N][N],Map[N][N];
 7 int flag[N][N],dis[N][N];
 8 
 9 void pre_work(int x[N][N],int y[N][N],int z[N][N])
10 {
11     for(int i=0;i<n;i++)
12     {
13         for(int j=0;j<n;j++)
14         {
15             flag[i][j]=INF;
16             for(int k=0;k<n;k++)
17                 flag[i][j]=min(flag[i][j],x[i][k]+y[k][j]);
18         }
19     }
20     for(int i=0;i<n;i++)
21         for(int j=0;j<n;j++) z[i][j]=flag[i][j];
22 }
23 
24 int main()
25 {
26     ios::sync_with_stdio(false);
27     cin.tie(0);
28     cin>>T;
29     while(T--)
30     {
31         cin>>n>>m;
32         for(int i=0;i<n;i++)
33         {
34             for(int j=0;j<n;j++) Map[i][j]=INF;
35         }
36         while(m--)
37         {
38             cin>>u>>v>>w;
39             Map[u-1][v-1]=min(Map[u-1][v-1],w);
40         }
41         
42         for(int i=0;i<n;i++)
43         {
44             for(int j=0;j<n;j++) 
45                 a[0][i][j]=b[0][i][j]= i==j? 0:INF;
46         }
47         for(int i=1;i<M;i++) pre_work(a[i-1],Map,a[i]);//处理出经过i步从 x->y 的最短路  
48         for(int i=1;i<M;i++) pre_work(b[i-1],a[100],b[i]);//处理出从 x->y 恰好走  100*i步
49         
50         //Floyd
51         for(int i=0;i<n;i++)
52         {
53             for(int j=0;j<n;j++) dis[i][j]= i==j? 0:Map[i][j];
54         }
55         for(int k=0;k<n;k++)
56         {
57             for(int i=0;i<n;i++)
58             {
59                 for(int j=0;j<n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
60             }
61         }
62         
63         for(int x=0;x<M;x++)
64         {
65             for(int i=0;i<n;i++)
66             {
67                 for(int j=0;j<n;j++)
68                 {
69                     flag[i][j]=INF;
70                     for(int k=0;k<n;k++) flag[i][j]=min(flag[i][j],b[x][i][k]+dis[k][j]); 
71                 }
72             }
73             for(int i=0;i<n;i++) for(int j=0;j<n;j++) b[x][i][j]=flag[i][j];    
74         }
75         
76         cin>>q;
77         while(q--)
78         {
79             cin>>s>>t>>K; s--,t--;
80             int r=K/100,l=K%100,ans=INF;
81             for(int i=0;i<n;i++) ans=min(ans,b[r][s][i]+a[l][i][t]);
82             if(ans>=INF) cout<<-1<<endl;
83             else cout<<ans<<endl;
84         }    
85     }
86     
87     return 0;
88 }
89 　　
90 
91

View Code

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

推荐阅读