当前位置: 首页 > news >正文

洛谷P5304 [GXOI/GZOI2019] 旅行者(二进制分类技巧)

假设我们把特殊点分成 A,B 两个集合,新建 s 连 A 集合的所有点,边权 0 ,新建 t 连接 B 集合里的所有点,边权 0 ,那么 s 到 t 的最短路就是 A,B 集合点之间的最短路的最小值。

那么对于 k 个特殊点,我们枚举二进制里的第 i 位,把二进制第 i 位是 0 的点放在 A , 1 的点放在 B ,用以上方法跑一个最短路。

然后跑 log n 次最短路之后,所有最短路的最小值就是最终答案。

原理是,假设 k 个特殊点里最近的是 x 和 y ,那么 x 和 y 一定有一个二进制位不一样,那么他们肯定在那次分组的时候被放进了不同的集合,从而肯定被算进了最后的答案之中最短路。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
typedef pair<LL,LL> PLL;
const int N=1e5+10,M=5e5+10;
int a[N];
int n,m,k,s,t;
LL dist[N];
vector<vector<PLL>> edges;
vector<vector<PLL>> nw;
LL dijkstra(){memset(dist,0x3f,sizeof(dist));auto cmp=[](PLL& x,PLL& y){return x.second>y.second;};priority_queue<PLL,vector<PLL>,decltype(cmp)> heap(cmp);heap.push({s,0});dist[s]=0;while(heap.size()){auto tmp=heap.top();int u=tmp.first;LL d=tmp.second;heap.pop();if(d>dist[u])continue;for(auto &[v,w]:nw[u]){if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;heap.push({v,dist[v]});}}}return dist[t];
}
void solve(){cin>>n>>m>>k;edges=vector<vector<PLL>>(n+5,vector<PLL>(0));for(int i=1;i<=m;i++){LL x,y,z;cin>>x>>y>>z;edges[x].push_back({y,z});}for(int i=1;i<=k;i++){cin>>a[i];}s=n+1;t=n+2;LL ans=~0ull>>1;for(int i=0;(1<<i)<=k;i++){nw=edges;for(int j=1;j<=k;j++){if((j>>i)&1)nw[s].push_back({a[j],0});elsenw[a[j]].push_back({t,0});}ans=min(ans,dijkstra());nw=edges;for(int j=1;j<=k;j++){if((j>>i)&1)nw[a[j]].push_back({t,0});elsenw[s].push_back({a[j],0});}ans=min(ans,dijkstra());}cout<<ans<<endl;
}
int main(){cin.tie(nullptr)->sync_with_stdio(false);int T;cin>>T;while(T--){solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=26327

相关文章:

  • 英语_阅读_AI Robot_待读
  • 【C++】AVL树的概念及完成(万字图文超详解)
  • 打造自主学习的AI Agent:强化学习+LangGraph代码示例
  • 关于二分
  • NKOJ全TJ计划——NP11721
  • 印度全球能力中心2030年展望与技术基建规划
  • NOI Linux 食用教程
  • 详细介绍:基于 Android 和 JBox2D 的简单小游戏
  • 基于深度学习的语音识别高效的系统设计与实现
  • CF2152H2 Victorious Coloring (Hard Version) 题解
  • 题解:P6162 [Cnoi2020] 四角链
  • 题解:P3301 [SDOI2013] 方程
  • # 20232321 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • 题解:CF1292E Rin and The Unknown Flower
  • 打印A3大小的PDF文件为A4幅面
  • 课程总结2
  • 解码查找算法与哈希表
  • 第二次课动手动脑合集
  • centos8的防火墙管理
  • 如何生成和制作PDF文件 - 实践
  • 1.2 马尔可夫决策过程(Markov Decision Process, MDP)
  • 博弈论dp复习笔记
  • 10.7阅读笔记
  • 如果你的微信支付界面出现“摇一摇”,说明你的隐私正在泄露
  • 多线程和网络总结
  • 8.RV1126-OPENCV 视频中添加LOGO - 指南
  • 学习记录:响应式系统、文件通知与游戏输入机制的异同
  • oppoR9m刷Linux系统: 制作 scatter.txt 和 导出手机preloader
  • 详细介绍:ASR技术(自动语音识别)深度解析
  • 1.1 采样问题 Sampling and Bandits