2020多校3 1007 Tokitsukaze and Rescue 最短路，搜索，暴力-白红宇的个人博客

2020多校3 1007 Tokitsukaze and Rescue 最短路，搜索，暴力

发布日期：2021-05-10 11:28:54 浏览次数：20 分类：精选文章

本文共 1357 字，大约阅读时间需要 4 分钟。

题目链接

题意

节点数小于50的双向强联通图，最多有k次（k小于5）机会删除某一边

问删除k条边后最短路的最大值是多少。

思路

时限八秒，节点50，最多五次机会，数据随机生成，暴力就完事了奥里给！

易知若想让最短路变大，则每次都应该在最短路径上删除边，那么记录最短路，每次删除一条边跑dfs。注意记录最短路径的数组每一次都需要重新开，只开一个会来回覆盖

教训/收获

看见数据量小，时间宽松的就勇敢打暴力，做题一定注意数据范围，时限，有很多信息

头一次用邻接矩阵写dij，dij跑的dis数组和输入的数组要分开记录，，

代码

#include
   
    #include
    
     #include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
              #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define endl "\n"#define int long long//#define double long doubleusing namespace std; typedef long long ll; const int maxn=55; const long long inf=0x3f3f3f3f3f3f3f3f; int n,m; int dis[maxn][maxn]; int dij[maxn]; int ans; typedef pair
             
               P; int dijs(int s,int *pre){ priority_queue
              
               ,greater
                > q; memset(dij,0x3f,sizeof dij); dij[s]=0; q.push(P(0,s)); while(!q.empty()){ P p=q.top(); q.pop(); int u=p.second; if(dij[u]
                
                 dij[u]+dis[u][i]){ dij[i]=dij[u]+dis[u][i]; pre[i]=u; q.push({ dij[i],i}); } } } return dij[n]; } void solve(int x){ int p[maxn]; if(!x){ ans=max(ans,dijs(1,p)); return ; } dijs(1,p); int u=n,v; while(u!=1){ v=p[u]; int tmp=dis[u][v]; dis[u][v]=dis[v][u]=inf; solve(x-1); dis[u][v]=dis[v][u]=tmp; u=v; } } signed main(){ IOS int tn; cin>>tn; while(tn--){ ans=0; cin>>n>>m; for(int i=1;i<=(n-1)*n/2;i++){ int u,v,w; cin>>u>>v>>w; dis[u][v]=dis[v][u]=w; } solve(m); cout<
                 
                  <

上一篇：Acwing 860 二分图判断模版题染色法

下一篇：2020多校3 1004 Tokitsukaze and Multiple

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目链接

题意

思路

教训/收获

代码

发表评论

最新留言

关于作者

推荐文章