「bsoj4496」关于女朋友 - 最短路径树+倍增 | Bill Yang's Blog

「bsoj4496」关于女朋友 - 最短路径树+倍增

题目大意

给出一个图,要求多次询问从1出发至少往$x[i]$沿最短路走$k[i]$条边或走$t[i]$分钟,然后走到$n$的最少时间。
注:往$x[i]$走的不算做要求输出的时间。


题目分析

从1开始建立最短路径树,并预处理出每个点到达$n$的最短路径长度。
接着用Sparse_Table稀疏表预处理出树上的$k$倍祖先及到达$k$倍祖先路径上走到$n$的最短路径最小值。
对于给定的询问,我们爬爬树即可。

思路应该比较显然吧,代码也比较好写。

注:可以不用把最短路径树建出来,否则建出来使用Dfs会爆栈


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
int n,m,q,dist[maxn],vst[maxn],p[maxn][35],f[maxn][35],Depth[maxn];
struct Edge {
int from,to,dist,dist2;
};
vector<Edge>edges[maxn];
void AddEdge(int x,int y,int v,int v2) {
edges[x].push_back((Edge) {
x,y,v,v2
});
}
struct HeapNode {
int d,u;
bool operator < (const HeapNode& b) const {
return d>b.d;
}
};
void Dijkstra(int s) {
priority_queue<HeapNode>Q;
for(int i=1; i<=n; i++)dist[i]=0x7fffffff/2,vst[i]=0;
dist[s]=0;
Q.push((HeapNode) {
0,s
});
while(!Q.empty()) {
int Now=Q.top().u;
Q.pop();
if(vst[Now])continue;
vst[Now]=1;
for(int i=0; i<edges[Now].size(); i++) {
Edge& e=edges[Now][i];
int Next=e.to;
if(dist[Next]>dist[Now]+e.dist) {
dist[Next]=dist[Now]+e.dist;
Q.push((HeapNode) {
dist[Next],Next
});
}
}
}
}
void Sparse_Table() {
queue<int>Q;
Q.push(1);
for(int i=1; i<=n; i++)
for(int j=0; j<=log2(n); j++) {
p[i][j]=-1;
if(j!=0)f[i][j]=0x7fffffff/2;
}
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int i=1; i<=log2(n); i++)
if(p[Now][i-1]!=-1) {
p[Now][i]=p[p[Now][i-1]][i-1];
f[Now][i]=min(f[p[Now][i-1]][i-1],f[Now][i-1]);
}
for(int i=0; i<edges[Now].size(); i++) {
Edge& e=edges[Now][i];
int Next=e.to;
if(dist[Now]+e.dist==dist[Next]) {
p[Next][0]=Now;
Depth[Next]=Depth[Now]+1;
Q.push(Next);
}
}
}
}
int Solve1(int x,int k) {
if(Depth[x]<k)return -1;
int Min=0x7fffffff/2;
for(int i=log2(n); i>=0; i--)
if(p[x][i]!=-1&&Depth[p[x][i]]>=k) {
Min=min(Min,f[x][i]);
x=p[x][i];
}
return min(Min,f[x][0]);
}
int Solve2(int x,int t) {
if(dist[x]<t)return -1;
int Min=0x7fffffff/2;
for(int i=log2(n); i>=0; i--)
if(p[x][i]!=-1&&dist[p[x][i]]>=t) {
Min=min(Min,f[x][i]);
x=p[x][i];
}
return min(Min,f[x][0]);
}
int main() {
n=Get_Int();
m=Get_Int();
q=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v1=Get_Int(),v2=Get_Int();
AddEdge(x,y,v2,v1);
AddEdge(y,x,v2,v1);
}
Dijkstra(n);
for(int Now=1; Now<=n; Now++)
for(int i=0; i<edges[Now].size(); i++)
edges[Now][i].dist=edges[Now][i].dist2;
for(int i=1; i<=n; i++)f[i][0]=dist[i];
Dijkstra(1);
Sparse_Table();
dist[0]=Depth[0]=-1;
for(int i=1; i<=q; i++) {
int opt=Get_Int(),x=Get_Int(),y=Get_Int();
if(opt==1)printf("%d\n",Solve1(x,y));
else printf("%d\n",Solve2(x,y));
}
return 0;
}
本篇文章有用吗?有用还不快点击!
0%