2018 宁夏省赛 F. Moving On

程序员艳珂技术 2022年11月18日

0 收藏 456 点赞 4,952 浏览 1154 个字

题目链接 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 的最短路图。

 #include<bits/stdc++.h>
 #define EPS 1e-9
 using namespace std; typedef long long ll;
 const int INF=0x3f3f3f3f;
 const int MAXN=; int rob[];
 int dp[][][];
 int id[]; bool cmp(int i,int j){
     return rob[i]<rob[j];
 } int main(){
     int Tests;
     scanf("%d",&Tests);
     for(int cntT=;cntT<=Tests;++cntT){
         memset(dp,INF,sizeof(dp));
         int N,Q;
         scanf("%d%d",&N,&Q);
         for(int i=;i<=N;++i){
             id[i]=i;
             scanf("%d",&rob[i]);
         }
         sort(id+,id+N+,cmp);         for(int i=;i<=N;++i)
             for(int j=;j<=N;++j)
                 scanf("%d",&dp[][i][j]);
         for(int k=;k<=N;++k){
           int rk=id[k];
           for(int i=;i<=N;++i)
             for(int j=;j<=N;++j) {
                 dp[k][i][j]=min(dp[k-][i][j],dp[k-][i][rk]+dp[k-][rk][j]);
             }
         }
         printf("Case #%d:\n",cntT);
         for(int q=;q<=Q;++q){
             int u,v,dan;
             scanf("%d%d%d",&u,&v,&dan);
             int k=;
             for(int i=;i<=N;++i)
                 if(rob[id[i]]<=dan) k=i;
             printf("%d\n",dp[k][u][v]);
         }
     }
     return ;
 }