原题传送门
题意:给你k个点,让你求两两最短路之间的最小值
我们考虑二进制拆分,使得每两个点都有机会分在不同的组\((A:0,B:1)\)中,从源点\(S\)向\(A/B\)中的点连边权为0的边,从\(B/A\)中的点向汇点\(T\)连边权为0的边,这时\(S->T\)的最短路就是\(A/B\)中的点到\(B/A\)中的点最短路的最小值
所以做最短路次数为\(2\log k\),总复杂度为\(T n \log n\log k\)(srf好像还有少一个log的做法,orz srf)
#include <bits/stdc++.h>
#define ll long long
#define N 100005
#define M 700005
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register ll x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline ll Min(register ll a,register ll b)
{
return a<b?a:b;
}
struct edge{
int to,next,w;
}e[M];
int head[N],cnt,headn[N],cntn;
inline void add(register int u,register int v,register int w)
{
e[++cnt]=(edge){v,head[u],w};
head[u]=cnt;
}
inline void addn(register int u,register int v,register int w)
{
e[++cntn]=(edge){v,headn[u],w};
headn[u]=cntn;
}
int T,n,m,k,p[N],s,t;
ll dis[N];
inline ll dijkstra()
{
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
priority_queue<pair<ll,int> >q;
q.push(make_pair(0,s));
for(register int i=1;i<n+2;++i)
{
while(!q.empty()&&dis[q.top().second]!=-q.top().first)
q.pop();
if(q.empty())
break;
int now=q.top().second;
q.pop();
for(register int i=headn[now];i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]>dis[now]+e[i].w)
q.push(make_pair(-(dis[v]=dis[now]+e[i].w),v));
}
}
return dis[t];
}
int main()
{
int T=read();
while(T--)
{
cnt=0;
memset(head,0,sizeof(head));
n=read(),m=read(),k=read();
for(register int i=1;i<=m;++i)
{
int u=read(),v=read(),w=read();
add(u,v,w);
}
for(register int i=1;i<=k;++i)
p[i]=read();
ll ans=~0ull>>1;
s=n+1,t=n+2;
for(register int i=0;(1<<i)<=k;++i)
{
cntn=cnt;
memcpy(headn,head,sizeof(head[0])*(n+3));
for(register int j=1;j<=k;++j)
if(j&(1<<i))
addn(p[j],t,0);
else
addn(s,p[j],0);
ans=Min(ans,dijkstra());
cntn=cnt;
memcpy(headn,head,sizeof(head[0])*(n+3));
for(register int j=1;j<=k;++j)
if(j&(1<<i))
addn(s,p[j],0);
else
addn(p[j],t,0);
ans=Min(ans,dijkstra());
}
write(ans),puts("");
}
return 0;
}
【题解】Luogu P5304 [GXOI/GZOI2019]旅行者的更多相关文章
-
luogu P5304 [GXOI/GZOI2019]旅行者
传送门 所以这个\(5s\)是SMG 暴力是枚举每一个点跑最短路,然后有一个很拿衣服幼稚的想法,就是把所有给出的关键点当出发点,都丢到队列里,求最短路的时候如果当前点\(x\)某个相邻的点\(y\)是 ...
-
P5304 [GXOI/GZOI2019]旅行者
题目地址:P5304 [GXOI/GZOI2019]旅行者 这里是官方题解 一个图 \(n\) 点 \(m\) 条边,里面有 \(k\) 个特殊点,问这 \(k\) 个点之间两两最短路的最小值是多少? ...
-
洛谷 P5304 [GXOI/GZOI2019]旅行者(最短路)
洛谷:传送门 bzoj:传送门 参考资料: [1]:https://xht37.blog.luogu.org/p5304-gxoigzoi2019-lv-xing-zhe [2]:http://www ...
-
P5304 [GXOI/GZOI2019]旅行者(最短路/乱搞)
luogu bzoj Orz自己想出神仙正解的sxy 描述略 直接把所有起点推进去跑dijkstra... 并且染色,就是记录到这个点的最短路是由哪个起点引导出来的 然后再把所有边反指跑一次... 之 ...
-
[洛谷P5304][GXOI/GZOI2019]旅行者
题目大意: 有一张 \(n(n\leqslant10^5)\) 个点 \(m(m\leqslant5\times10^5)\) 条边的有向有正权图,有$k(2\leqslant k\leqslant ...
-
【BZOJ5506】[GXOI/GZOI2019]旅行者(最短路)
[BZOJ5506][GXOI/GZOI2019]旅行者(最短路) 题面 BZOJ 洛谷 题解 正着做一遍\(dij\)求出最短路径以及从谁转移过来的,反过来做一遍,如果两个点不由同一个点转移过来就更 ...
-
[LOJ3087][GXOI/GZOI2019]旅行者——堆优化dijkstra
题目链接: [GXOI/GZOI2019]旅行者 我们考虑每条边的贡献,对每个点求出能到达它的最近的感兴趣的城市(设为$f[i]$,最短距离设为$a[i]$)和它能到达的离它最近的感兴趣的城市(设为$ ...
-
【题解】Luogu P5301 [GXOI/GZOI2019]宝牌一大堆
原题传送门 首先先要学会麻将,然后会发现就是一个暴力dp,分三种情况考虑: 1.非七对子国士无双,设\(dp_{i,j,k,a,b}\)表示看到了第\(i\)种牌,一共有\(j\)个\(i-1\)开头 ...
-
【题解】Luogu P5300 [GXOI/GZOI2019]与或和
原题传送门 我们珂以拆位,拆成一个个0/1矩阵 贡献珂以用全0,全1的子矩阵的个数来计算 全0,全1的子矩阵的个数珂以用悬线法/单调栈解决 #include <bits/stdc++.h> ...
随机推荐
-
PostgreSQL Replication之第十三章 使用PL/Proxy扩展(3)
13.3 聪明地扩展与处理集群 建立集群不是您面临的唯一任务.如果所有的事情都做完了并且系统已经运行了,您可能需要到处调整配置. 13.3.1 添加和移动分区 一旦一个集群启动并运行,您可能会发现您的 ...
-
golang的哪些坑爷事: package实践
在golang中package是个困惑的概念, 特别是package还可以与folder不同名, 委实让我恶心了一把. 关于golang的package的最佳实践: package is folder ...
-
使用LINQ 對List分頁/區
listview之類的服務器控件分頁自不用多說,拖拖控件改改屬性分分鐘的事.就不浪費大家時間了. 這裏只寫大概思路及關鍵代碼了. LINQ裏有一個對集合進行分區的操作可用於分頁. page ...
-
Android(java)学习笔记220:开发一个多界面的应用程序之界面间数据传递
1.界面跳转的数据传递 (1)intent.setData() --> intent.getData(): 传递的数据比较简单,一般是文本类型的数据String:倘若我们传递的数据比较复 ...
-
JAVA FILE or I/O学习 - File学习
public class FileKnow { public static void main(String[] args) { //构建file对象 ,参数表示文件所在的路径 File file = ...
-
DB 查询分析器 6.03 在Windows 8 上安装与运行演示
DB 查询分析器 6.03 在Windows 8 上安装与运行演示 马根峰 ( 广东联合电子服务股份有限公司, 广州 510300) 摘要 ...
-
python读取文件时提示";UnicodeDecodeError: &#39;gbk&#39; codec can&#39;t decode
解决办法1. FILE_OBJECT= open('order.log','r', encoding='UTF-8') 解决办法2. FILE_OBJECT= open('order.log','rb ...
-
Spring JDBC RowMapper接口示例
JdbcTemplate类使用org.springframework.jdbc.core.RowMapper <T>接口在每行的基础上映射ResultSet的行.该接口的实现执行将每行映射 ...
-
11.Proxy
Proxy Proxy 概述 Proxy 用于修改某些操作的默认行为,等同于在语言层面做出修改,所以属于一种"元编程"(meta programming),即对编程语言进行编程. ...
-
Sheldon Numbers GYM -- 枚举
Sheldon Numbers GYM 题意:定义Sheldon Number为其二进制数是ABA……ABA型的或者ABAB……AB的,其中A全为1,B全为0(A>0, B>0),问[m, ...