当前位置:网站首页>Cf464e the classic problem [shortest path, chairman tree]
Cf464e the classic problem [shortest path, chairman tree]
2022-07-06 03:44:00 【QuantAsk】
On the subject
Topic link :https://www.luogu.com.cn/problem/CF464E
The main idea of the topic
n n n A little bit m m m An undirected graph with edges , The first i i i The length of the strip is 2 x i 2^{x_i} 2xi, seek s s s To t t t One of the most short circuit .
1 ≤ n ≤ 1 0 5 , 0 ≤ m , x i ≤ 1 0 5 1\leq n\leq 10^5,0\leq m,x_i\leq 10^5 1≤n≤105,0≤m,xi≤105
Their thinking
shortest path , But maintain binary weights with the chairman tree .
One position plus 1 1 1 When we start with him, we put him back 1 1 1 All become 0 0 0, Then these 0 0 0 In front of the 1 1 1 Just fine .
Compare the size, and find the first different position from high to low , To achieve this function, we can maintain a h a s h hash hash.
Then reload these two operations and you can run directly dij \text{dij} dij Just fine .
Time complexity : O ( n log 2 n ) O(n\log^2 n) O(nlog2n)
There are also natural overflow hashes. Don't use them 2 2 2 Idempotent number
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ull unsigned long long
using namespace std;
const int N=1e5+100,M=(N+10)<<6,P=1e9+7;
struct edge{
int to,next,w;
}a[N<<1];
int n,m,s,t,ans,tot,ls[N],rt[N],pre[N],c[N];
ull pw[N+10],one[N+10];bool v[N];
struct SegTree{
ull w[M];int cnt=1,ls[M],rs[M];
bool CMP(int x,int y,int L,int R){
if(w[x]==w[y])return 0;
if(L==R)return w[x]<w[y];
int mid=(L+R)>>1;
if(w[rs[x]]==w[rs[y]])return CMP(ls[x],ls[y],L,mid);
return CMP(rs[x],rs[y],mid+1,R);
}
int Make(int x,int &now,int L,int R,int st){
if(L>=st&&w[x]==one[R-L+1])
{
now=0;return 0;}
now=++cnt;w[now]=w[x];
ls[now]=ls[x];rs[now]=rs[x];
if(L==R){
w[now]=1;return L;}
int mid=(L+R)>>1;int flag=0;
if(L>=st){
if(w[ls[x]]==one[mid-L+1]){
ls[now]=0;
flag=Make(rs[x],rs[now],mid+1,R,st);
}
else flag=Make(ls[x],ls[now],L,mid,st);
}
else{
if(st<=mid)flag=Make(ls[x],ls[now],L,mid,st);
if(!flag)flag=Make(rs[x],rs[now],mid+1,R,st);
}
w[now]=w[ls[now]]+w[rs[now]]*pw[mid-L+1];
return flag;
}
void Get(int x,int L,int R){
if(L==R){
ans=(2ll*ans+w[x])%P;return;}
int mid=(L+R)>>1;
Get(rs[x],mid+1,R);
Get(ls[x],L,mid);
}
}T;
struct node{
int id,rt;
};
bool operator<(const node &x,const node &y)
{
return T.CMP(y.rt,x.rt,0,N);}
priority_queue<node> q;
void addl(int x,int y,int w){
a[++tot].to=y;
a[tot].next=ls[x];
ls[x]=tot;a[tot].w=w;
return;
}
void Dij(){
rt[s]=c[s]=1;q.push((node){
s,rt[s]});
while(!q.empty()){
int x=q.top().id;q.pop();
if(v[x])continue;v[x]=1;
if(x==t)return;
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(v[y])continue;
int nr;T.Make(rt[x],nr,0,N,a[i].w);
if((!c[y])||T.CMP(nr,rt[y],0,N))
{
pre[y]=x;c[y]=c[x]+1;rt[y]=nr;q.push((node){
y,nr});}
}
}
}
void print(int x){
if(pre[x])print(pre[x]);
printf("%d ",x);
}
int main()
{
// freopen("base.in","r",stdin);
// freopen("base.out","w",stdout);
scanf("%d%d",&n,&m);pw[0]=1;
for(int i=1;i<N+10;i++)
pw[i]=pw[i-1]*131ull,one[i]=one[i-1]*131ull+1ull;
for(int i=1;i<=m;i++){
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
if(x==16&&y==24&&m==197)
printf("%d ",v);
addl(x,y,v);addl(y,x,v);
}
scanf("%d%d",&s,&t);
Dij();
if(!c[t])return puts("-1")&0;
T.Get(rt[t],0,N);
printf("%d\n%d\n",ans,c[t]);
print(t);putchar('\n');
return 0;
}
边栏推荐
- Redo file corruption repair
- Multi project programming minimalist use case
- Why do you want to start pointer compression?
- Pytorch基础——(1)张量(tensor)的初始化
- After five years of testing in byte, I was ruthlessly dismissed in July, hoping to wake up my brother who was paddling
- Recommended papers on remote sensing image super-resolution
- Exness foreign exchange: the governor of the Bank of Canada said that the interest rate hike would be more moderate, and the United States and Canada fell slightly to maintain range volatility
- cookie,session,Token 这些你都知道吗?
- Factors affecting user perception
- 2. GPIO related operations
猜你喜欢
施努卡:3d视觉检测应用行业 机器视觉3d检测
Canvas cut blocks game code
Brush questions in summer -day3
Esbuild & SWC: a new generation of construction tools
[meisai] meisai thesis reference template
SAP ALV颜色代码对应颜色(整理)
How do we make money in agriculture, rural areas and farmers? 100% for reference
Flask learning and project practice 9: WTF form verification
Factors affecting user perception
教你用Pytorch搭建一个自己的简单的BP神经网络( 以iris数据集为例 )
随机推荐
Recommended papers on remote sensing image super-resolution
在字节做测试5年,7月无情被辞,想给划水的兄弟提个醒
SAP ALV单元格级别设置颜色
Do you know cookies, sessions, tokens?
C#(二十七)之C#窗体应用
给新人工程师组员的建议
pytorch加载数据
three.js网页背景动画液态js特效
C#(三十一)之自定义事件
Schnuka: what is visual positioning system and how to position it
How do we make money in agriculture, rural areas and farmers? 100% for reference
Blue Bridge Cup - day of week
Image super-resolution using deep convolutional networks(SRCNN)解读与实现
Quartz misfire missed and compensated execution
Why do you want to start pointer compression?
施努卡:3d视觉检测应用行业 机器视觉3d检测
Failure causes and optimization methods of LTE CSFB
Canvas cut blocks game code
MySQL 中的数据类型介绍
BUAA计算器(表达式计算-表达式树实现)