题意
给定一张无向图, 每条边有一个距离和一个高度. 再给定 $q$ 组可能在线的询问, 每组询问给定一个点 $v$ 和一个高度 $h$, 鸭子德可以先无需花费地在高度大于 $h$ 的边上任意行动, 然后可以在任意点开始以花费等于距离的模式行动. 问最小的花费.
$|V|\le 2\times 10^5,|E|\le 4\times 10^5,q\le 4\times 10^5,h\le 10^9$.
题解
显然带花费部分的行动是一个单源最短路. 那么我们只要求出无花费部分的行动可以到达的点中哪一个点距离 $1$ 最近就可以了.
发现无花费部分是个类似瓶颈路的问题, 我们可以在 Kruskal 重构树上倍增求出能到达的点所组成的子树, 输出这个子树中的点到 $1$ 的最短距离就可以了.
为啥我要写这个裸题的题解呢?
一个原因是存板子, 另一个原因是这个沙雕强制在线把我卡掉了 $3$ 分qaq…具体情况
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
#include <bits/stdc++.h>
const int MAXV=4e5+10;
const int MAXE=1e6+10;
struct Edge{
int from;
int to;
int dis;
int pos;
Edge* next;
bool friend operator>(const Edge& a,const Edge& b){
return a.pos>b.pos;
}
};
Edge E[MAXE];
Edge Ex[MAXE];
Edge* head[MAXV];
Edge* top=E;
int v;
int e;
int q;
int n;
int k;
int maxv;
int dis[MAXV];
int pos[MAXV];
int ufs[MAXV];
bool vis[MAXV];
int pprt[20][MAXV];
int* prt=pprt[0];
int ReadInt();
void Kruskal();
int FindRoot(int);
void Dijkstra(int);
void Insert(int,int,int,int);
int main(){
int T=ReadInt();
while(T--){
memset(pprt,0,sizeof(pprt));
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
top=E;
n=v=ReadInt();
e=ReadInt();
for(int i=0;i<e;i++){
int a=ReadInt(),b=ReadInt(),c=ReadInt(),d=ReadInt();
Ex[i]=Edge({a,b,c,d,NULL});
Insert(a,b,c,d);
Insert(b,a,c,d);
}
q=ReadInt(),k=ReadInt(),maxv=ReadInt();
Dijkstra(1);
Kruskal();
int lg=0;
for(int i=1;(1<<i)<=v;i++){
lg=i;
for(int j=1;j<=v;j++)
pprt[i][j]=pprt[i-1][pprt[i-1][j]];
}
int lastans=0;
while(q--){
int s=(0ll+ReadInt()+k*lastans-1)%n+1,h=(0ll+ReadInt()+k*lastans)%(maxv+1);
for(int i=lg;i>=0;i--){
if(pos[pprt[i][s]]>h)
s=pprt[i][s];
}
printf("%d\n",lastans=dis[s]);
}
}
return 0;
}
void Kruskal(){
std::sort(Ex,Ex+e,std::greater<Edge>());
for(int i=1;i<=v;i++)
ufs[i]=i;
int& cur=v;
for(int i=0;i<e;i++){
int a=FindRoot(Ex[i].from);
int b=FindRoot(Ex[i].to);
if(a!=b){
++cur;
pos[cur]=Ex[i].pos;
dis[cur]=std::min(dis[a],dis[b]);
prt[a]=cur;
prt[b]=cur;
ufs[cur]=cur;
ufs[a]=cur;
ufs[b]=cur;
}
}
}
void Dijkstra(int s){
std::priority_queue<std::pair<int,int>> q;
memset(dis,0x7F,sizeof(dis));
dis[s]=0;
q.emplace(0,s);
while(!q.empty()){
s=q.top().second;
q.pop();
if(vis[s])
continue;
vis[s]=true;
for(Edge* i=head[s];i!=NULL;i=i->next){
if(dis[i->to]>dis[s]+i->dis){
dis[i->to]=dis[s]+i->dis;
q.emplace(-dis[i->to],i->to);
}
}
}
}
inline void Insert(int from,int to,int dis,int pos){
top->from=from;
top->to=to;
top->dis=dis;
top->pos=pos;
top->next=head[from];
head[from]=top++;
}
int FindRoot(int x){
return ufs[x]==x?ufs[x]:ufs[x]=FindRoot(ufs[x]);
}
inline int ReadInt(){
int x=0;
register char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
|
