2018 宁夏省赛 F. Moving On

题目链接 https://nanti.jisuanke.com/t/28406

大意是有n(<=200)个城市，城市间有路(Input给了邻接矩阵) 每个城市有一个危险值，然后是q(2e4)个询问，每个询问给了 u，v ，w ，对于每个询问回答u到v的最短路长度(最短路过程中不得经过危险值超过w的城市，ps不含首尾)

开始看见邻接矩阵的形式猜了用Floyd写，想的是每次询问跑一次最短路(循环k时避过危险值超过w的点)，但q有2e4，会TLE；后来又想每次询问跑一遍Dijkstra(改造后的不经过危险值超出的点)，以为Dijkstra能快一点，但还是TLE了。

正确的做法还是Floyd，按危险值从小到大排序城市编号(间接排序)，然后用的dp[][][]记录最短路。

dp[k][i][j]表示添加(第1~k小的危险值的城市后)的 i->j 最短路。(其实就是Floyd三维未降维的版本)

然后针对每个询问找到它的最大k 的最短路图。

 1 #include<bits/stdc++.h>
 2 #define EPS 1e-9
 3 using namespace std;
 4 
 5 typedef long long ll;
 6 const int INF=0x3f3f3f3f;
 7 const int MAXN=211;
 8 
 9 int rob[211];
10 int dp[211][211][211];
11 int id[211];
12 
13 bool cmp(int i,int j){
14     return rob[i]<rob[j];
15 }
16 
17 int main(){
18     int Tests;
19     scanf("%d",&Tests);
20     for(int cntT=1;cntT<=Tests;++cntT){
21         memset(dp,INF,sizeof(dp));
22         int N,Q;
23         scanf("%d%d",&N,&Q);
24         for(int i=1;i<=N;++i){
25             id[i]=i;
26             scanf("%d",&rob[i]);
27         }
28         sort(id+1,id+N+1,cmp);
29 
30         for(int i=1;i<=N;++i)
31             for(int j=1;j<=N;++j)
32                 scanf("%d",&dp[0][i][j]);
33         for(int k=1;k<=N;++k){
34           int rk=id[k];
35           for(int i=1;i<=N;++i)
36             for(int j=1;j<=N;++j) {
37                 dp[k][i][j]=min(dp[k-1][i][j],dp[k-1][i][rk]+dp[k-1][rk][j]);
38             }
39         }
40         printf("Case #%d:
",cntT);
41         for(int q=1;q<=Q;++q){
42             int u,v,dan;
43             scanf("%d%d%d",&u,&v,&dan);
44             int k=0;
45             for(int i=1;i<=N;++i)
46                 if(rob[id[i]]<=dan) k=i;
47             printf("%d
",dp[k][u][v]);
48         }
49     }
50     return 0;
51 }

View Code

主要是熟悉Floyd原型。