题面：

K - Killing the Brute-force

给定标程和暴力在 n = 1, 2, . . . , m 时的运行时间，找到最小 的 n 使得三倍标程时限可以卡掉暴力 。
m很小没什么好讲的就一个遍历找到最小的即可

1
2
3
4
5
6
7
8
9
10
11
void solve(){
	int m;
	cin>>m;
	vector<int> a(m),b(m);
	for(int i = 0;i<m;++i) cin>>a[i];
	for(int i = 0;i<m;++i) cin>>b[i];
	for(int i = 0;i<m;++i)
		if(a[i]*3<b[i])
			return cout<<i + 1<<endl,void();
	cout<<-1<<endl;
}

A - AD 2020

给一个日期的区间，问有多少个日期含有子串“202”的。
2000.01.01 ≤ 日期 ≤ 9999.12.31
参考题解给的是直接打表然后O(1)回答，vp时队友是直接先打完表给它存数组里面结果代码过长cf交不上去……然后就乱搞了一下二分给他爆了。

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
 
int cnt=1;
string pre[44295];
 
bool isleap(int x){
    if(x%4==0 and x%100!=0 or x%400==0)return true;
    return false;
}
 
int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int lmon[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
 
void solve(){
    int y1,m1,d1,y2,m2,d2;
    cin>>y1>>m1>>d1>>y2>>m2>>d2;
 
    string sl=to_string(y1);
    if(m1<10)sl+="0";
    sl+=to_string(m1);
    if(d1<10)sl+="0";
    sl+=to_string(d1);
 
    string sr=to_string(y2);
    if(m2<10)sr+="0";
    sr+=to_string(m2);
    if(d2<10)sr+="0";
    sr+=to_string(d2);
 
    //小 -> 大
    int l=1,r=44294;
    while(l<r){//第一个大于等于sl的日期
        int mid=(l+r)>>1;
        if(pre[mid]<sl)l=mid+1;
        else r=mid;
    }
    int ansl=r;
 
    l=1,r=44294;
    while(l<r){//第一个小于等于sr的日期
        int mid=(l+r)>>1;
        if(pre[mid]>sr)r=mid-1;
        else l=mid;
        if(r==l+1)break;
    }
    if(pre[l+1]<=sr)l++;
    int ansr=l;
 
    cout<<ansr-ansl+1<<endl;
}

实际上直接在询问前预处理出来前缀和也不会超时的

I - Invoking the Magic

给定 n 对 pair，保证这 2n 个数一定由 n 个不同的数各出现 恰好两次构成。 将这些 pair 分成若干组，使得每组内出现的数都在该组内 出现恰好两次。 最小化最大的组包含的 pair 数。
n在1e5范围内。
如果按照关系建图就很容易发现是个连通块问题。直接离散化之后并查集即可。
这道题卡常居然，用stl离散化多写几个for直接t了，不知道当时比赛的测评机怎么样。

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
using ll=long long;
const int N=1e5+5;

int a[N],b[N],c[2*N],d[2*N];

void solve(){
    int n;
    cin>>n;

    per(i,1,n){
        cin>>a[i]>>b[i];
        //1 3 5 7 9
        int idx=(i-1)*2+1;
        c[idx]=a[i];
        c[idx+1]=b[i];
    }

    sort(c+1,c+1+2*n);
    int dcnt=1;
    d[dcnt++]=c[1];
    per(i,2,2*n){
        if(c[i]!=d[dcnt-1]){
            d[dcnt++]=c[i];
        }
    }
    //1~dnct-1

    map<int,int>f;
    per(i,1,dcnt-1){
        f[d[i]]=i;
    }

    per(i,1,n){
        a[i]=f[a[i]];
        b[i]=f[b[i]];
    }

    int g[dcnt];
    per(i,1,dcnt-1)g[i]=i;
    function<int(int)>find=[&](int x){
        if(g[x]==x)return x;
        else return g[x]=find(g[x]);
    };
    function<void(int,int)>unit=[&](int x,int y){
        int g1=find(g[x]),g2=find(g[y]);
        g[g1]=g2;
    };

    per(i,1,n){
        unit(a[i],b[i]);
    }

    int ans[dcnt];
    per(i,0,dcnt-1)ans[i]=0;

    per(i,1,dcnt-1)g[i]=find(g[i]);
    per(i,1,dcnt-1)ans[g[i]]++;

    per(i,1,dcnt-1){
        ans[0]=max(ans[i],ans[0]);
    }
    cout<<ans[0]<<endl;
}

B - Bin Packing Problem

模拟 Bin Packing 问题的两个近似算法： (1) FF：每次找到最靠左的可以放下该物品的背包。 (2) BF：每次找到剩余容量最小的可以放下该物品的背包。
n小于等于1e6。

逆天歪榜题。赛后看题解发现是官方的评级是一道有金牌难度的题。vp也没想多久就给它A了。
第二个算法很好想，就是map里面用二分即可。
第一个首先是有一个单调性，因为找的是最左边的，所以存在一个边界，边界的左边的最大值一定是小于物品大小，从1号背包开始到边界的任意右边的区间的最大值一定大于物品大小，很显然的二分，由于枚举物品就要O(n)复杂度了，然后正常的二分，check里面又是线段树区间查询，O(nlognlogn)是过不了1e6的，但是直接在线段树上做二分就没问题，能优化掉外围的一个log。
只能说板题学过就很简单

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
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>

#define endl '\n'
#define int long long
using namespace std;

template<class Info>
struct SegmentTree {
	int n;
	std::vector<Info> info;
	SegmentTree() : n(0) {}
	SegmentTree(int n_, Info v_ = Info()) {
		init(n_, v_);
	}
	template<class T>
	SegmentTree(std::vector<T> init_) {
		init(init_);
	}
	void init(int n_, Info v_ = Info()) {
		init(std::vector<Info>(n_, v_));
	}
	template<class T>
	void init(std::vector<T> init_) {
		n = init_.size();
		info.assign(4 << std::__lg(n), Info());
		std::function<void(int, int, int)> build = [&](int p, int l, int r) {
			if (r - l == 1) {
				info[p] = init_[l];
				return;
			}
			int m = (l + r) / 2;
			build(2 * p, l, m);
			build(2 * p + 1, m, r);
			pull(p);
		};
		build(1, 0, n);
	}
	void pull(int p) {
		info[p] = info[2 * p] + info[2 * p + 1];
	}
	void modify(int p, int l, int r, int x, const Info &v) {
		if (r - l == 1) {
			info[p] = v;
			return;
		}
		int m = (l + r) / 2;
		if (x < m) {
			modify(2 * p, l, m, x, v);
		} else {
			modify(2 * p + 1, m, r, x, v);
		}
		pull(p);
	}
	void modify(int p, const Info &v) {
		modify(1, 0, n, p, v);
	}
	Info rangeQuery(int p, int l, int r, int x, int y) {
		if (l >= y || r <= x) {
			return Info();
		}
		if (l >= x && r <= y) {
			return info[p];
		}
		int m = (l + r) / 2;
		return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
	}
	Info rangeQuery(int l, int r) {
		return rangeQuery(1, 0, n, l, r);
	}
	template<class F>
	int findFirst(int p, int l, int r, int x, int y, F pred) {
		if (l >= y || r <= x || !pred(info[p])) {
			return -1;
		}
		if (r - l == 1) {
			return l;
		}
		int m = (l + r) / 2;
		int res = findFirst(2 * p, l, m, x, y, pred);
		if (res == -1) {
			res = findFirst(2 * p + 1, m, r, x, y, pred);
		}
		return res;
	}
	template<class F>
	int findFirst(int l, int r, F pred) {
		return findFirst(1, 0, n, l, r, pred);
	}
};

struct Info {
	int maxn = 0;
};

Info operator+(Info a, Info b) {
	a.maxn = max(a.maxn,b.maxn);
	return a;
}


void solve() {
	int n,c;
	cin>>n>>c;
	vector<int> a(n);
	SegmentTree<Info> seg(n+5);
	for(int i = 0;i<n;++i){
		cin>>a[i];
	}
	int cnt = 1;
	seg.modify(0,Info{c});
	for(auto i: a){
		int l = seg.findFirst(0,cnt,[&](Info a){
			return a.maxn >= i;
		});
		if(l == -1){
			cnt++;
			seg.modify(cnt-1,Info{c - i});
		}else{
			int maxn = seg.rangeQuery(0,l+1).maxn;
			seg.modify(l,Info{maxn - i});
		}
	}
	cout<<cnt<<' ';
	cnt = 1;
	map<int,int> mp;
	mp[c] = 1;
	for(int i : a){
		auto t = mp.lower_bound(i);
		if(t == mp.end()){
			mp[c-i]++;
			cnt++;
			continue;
		}
		auto [x,y] = *t;
		if(--mp[x] == 0) mp.erase(x);
		mp[x-i]++;
	}
	cout<<cnt<<endl;
}

signed main() {
	cin.tie(nullptr), cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;
	int T = 1;
	cin>>T;
	while (T--) solve();
	return 0;
}

K - Killing the Brute-force

给这个dp转移方程
$dp[i][j]=\left\{\begin{array}{ll}
0 & (i=0) \\
i^{2}+d p[i-1][j] & (i>0, j=0) \\
i^{2}+\max (d p[i-1][j], d p[i-1][j-1]+b[i]) & (i>0, j>0)
\end{array}\right.$
给定一个序列 a1, a2, . . . , an，q 次询问，每次询问在 a 的某 个区间跑 DP 时某个状态的 DP 值
打表之后可以发现是a数组中[l,r]的最大个k个数字之和再加上 1² + 2² + · · · + (r − l + 1)²
就是主席树板子题。 

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
typedef long long ll;
const int N=2e5+10;
int rt[N],idx;
ll pre[N];
int a[N];
vector<int> num;
struct node{
    int l,r;
    int cnt;
    ll sum;
    ll d;
}tr[N*40];
int n;
void init(){
    pre[1]=1;
    for(ll i=2;i<=100005;i++)
        pre[i]=pre[i-1]+i*i;
}
void build(int &p,int l,int r){
    p=++idx;
    if(l==r){
        return ;
    }
    int mid=l+r>>1;
    build(tr[p].l,l,mid);
    build(tr[p].r,mid+1,r);
}
int find(int x){
    return lower_bound(num.begin(),num.end(),x)-num.begin()+1;
}
void insert(int &p,int q,int l,int r,int pos,int cnt){
    p=++idx,tr[p]=tr[q];
    tr[p].cnt+=1,tr[p].sum+=cnt;
    if(l==r){
        tr[p].d=cnt;
        return ;
    }
    int mid=l+r>>1;
    if(pos<=mid)
        insert(tr[p].l,tr[q].l,l,mid,pos,cnt);
    else
        insert(tr[p].r,tr[q].r,mid+1,r,pos,cnt);
}
ll query(int p,int q,int l,int r,int k){
    if(l==r){
        return tr[p].d*k;
    }
    int cnt=tr[tr[p].r].cnt-tr[tr[q].r].cnt;
    int mid=l+r>>1;
    if(k<=cnt){
        return query(tr[p].r,tr[q].r,mid+1,r,k);
    }
    else{
        return  tr[tr[p].r].sum-tr[tr[q].r].sum+query(tr[p].l,tr[q].l,l,mid,k-cnt);
    }
}
int main(){
    int t;
    cin>>t;
    init();
    while(t--){
        cin>>n;
        int i;
        idx=0;
        num.clear();
        for(i=1;i<=n;i++){
            scanf("%d",&a[i]);
            num.push_back(a[i]);
            rt[i]=0;
        }
        build(rt[0],1,n);
        sort(num.begin(),num.end());
        num.erase(unique(num.begin(),num.end()),num.end());
        for(i=1;i<=n;i++){
            insert(rt[i],rt[i-1],1,n,find(a[i]),a[i]);
        }
        int l,r,k;
        int q;
        cin>>q;
        while(q--){
            scanf("%d%d%d",&l,&r,&k);
            printf("%lld\n",pre[(r-l+1)]+query(rt[r],rt[l-1],1,n,k));
        }
    }
}

代码中54行原先板子求第k大是返回询问，这里改成求和即可。
出板题真的离大谱……既然B题已经是RMQ问题了为什么又出一道RMQ。虽然没学过主席树但是算法书上有区间第k大和前k个之和的例题，正式比赛两三个小时学一个算法和一道板题应该容易得吧

C - Crossword Validation

你得到了一个在N×N网格上完成的填字游戏。每个单元格要么是填有字母的白色单元格，要么是黑色单元格。你还会得到一本包含M个不同单词的字典，其中每个单词都有一个与之相关的分数。网格中的一个横向候选词是在网格的同一行上的一串连续的字母，不能被扩展。从形式上看，这意味着候选词最左边的单元格要么不存在，要么是一个黑色单元格，最右边的单元格也是如此。垂直候选词的定义与此类似，只是字母在同一列。候选词对于水平词来说是从左到右阅读，对于垂直词来说是从上到下阅读。当且仅当每个候选词都出现在给定的词典中时，该填字游戏才是有效的。一个有效的字谜的分数是字典中与每个候选词相关的分数之和。请注意，两个或多个候选词可能是相同的。在这种情况下，该词的分数会相应地被多次加分。你的程序必须确定谜题的分数，否则就报告说它无效。

输入包含多个案例。输入的第一行包含一个正整数 $T$ ，即样例数。
对于每个案例，输入的第一行包含两个整数 $N, M \ (1 \le N \le 1\,000, 1 \le M \le 4\times 10^6)$ ，即网格大小和字典中的字数。接下来的 $N$ 行分别包含长度为 $N$ 的字符串，其中每个字符都是小写英文字母或 “#”。如果$i$-th字符串中的 $j$-th 字符是 “#”，那么位于$i$-th 行和$j$-th 列交叉处的单元格为黑色单元格。否则，该字符表示该单元格中填写的字母。下面的 $M$ 行分别包含一个仅由小写英文字母组成的非空字符串，以及一个正整数，表示字典中的一个单词及其得分。保证这些 $M$ 个单词是成对不同的，每个单词的长度不超过 $N$ ，每个单词的得分不超过 $10^9$ 。
保证所有情况下 $N^2$ 的总和不超过 $4\times 10^6$ ，所有情况下字典中所有单词的长度总和不超过 $4\times 10^6$ 。
输出
对于每个案例，在单行中打印一个整数，即输入中给出的字谜解决方案的分数，如果它是有效的。如果解决方案无效，则打印-1。

评价为阅读理解题，读懂了就是一个字典树问题。
对字典中的单词建树。每个单词的末尾都改为对应的分数大小，即代码中的tot[now] = v。然后枚举所有的网格中的字符串，横着枚举一遍，竖着枚举一遍，如果有不匹配或者是一个单词的前缀（即结束时tot[now] == 0）那么就是无解输出-1，否则加上分数输出总分即可。
几个细节：
1.字典树的空间复杂度很高，对于习惯不好的人比如我直接#define int long long那么容易爆空间，最好还是算一下哪些变量会爆int，做这道题最终的总分会爆，不开long long会wa
2.字典树模板是求前缀，但是这道题如果是前缀（子串）也应该是返回非法，所以要判断!tot[now]。
其他就套模板即可。

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
#define N 4000006
using namespace std;

int n, m, nxt[N][30], cnt;
int tot[N];
char str[1003];
char mp[1003][10004];

int getNum(char x) {
	return x - 'a';
}

void insert(char s[], int v) {
	int len = (int) strlen(s), now = 0;
	for (int i = 0, x; i < len; ++i) {
		x = getNum(s[i]);
		if (!nxt[now][x]) nxt[now][x] = ++cnt;
		now = nxt[now][x];
//		++tot[now];
	}
	tot[now] += v;
}

int find(char s[]) {
	int len = (int) strlen(s), now = 0;
	for (int i = 0, x; i < len; ++i) {
		x = getNum(s[i]);
		if (!nxt[now][x]) return -1;
		else now = nxt[now][x];
	}
	if (!tot[now]) return -1;
	else return tot[now];
}


void solve() {
	cin >> n >> m;
	for (int i = 0; i <= cnt; i++) {
		memset(nxt[i], 0, sizeof nxt[i]);
		tot[i] = 0;
	}
	cnt = 0;
	for (int i = 1; i <= n; i++) 
		cin >> mp[i] + 1;
	for (int i = 1; i <= m; i++) {
		int v;
		cin >> str >> v;
		insert(str, v);
	}

	long long ans = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (mp[i][j] == '#') continue;
			int k = 0;
			while (mp[i][j] != '#' && j <= n)
				str[k++] = mp[i][j++];
			str[k] = 0;
			int res = find(str);
			if (~res) ans += res;
			else return cout << res << endl, void();
		}
	}
	for (int j = 1; j <= n; ++j) {
		for (int i = 1; i <= n; ++i) {
			if (mp[i][j] == '#') continue;
			int k = 0;
			while (mp[i][j] != '#' && i <= n)
				str[k++] = mp[i++][j];
			str[k] = 0;
			int res = find(str);
			if (~res) ans += res;
			else return cout << res << endl, void();
		}
	}
	cout << ans << endl;
}

signed main() {
	cin.tie(nullptr), cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.precision(10);
	cout << fixed;
	int T = 1;
	cin >> T;
	while (T--) solve();
	return 0;
}

G - Gliding

林克喜欢酷炫的挑战，比如从小孔射箭、从 3000 米高的雪山上滑下来，以及用一片巨大的树叶演奏音乐。现在他正在尝试一项新的挑战，在湖中滑行而不沉入湖中。
Link的世界是一个三维空间，我们定义一个笛卡尔坐标系 $(x,y,z)$ ，其中 $z$ 是高度。水面是平面 $z=0$ 。链接从位置 $(s_x,s_y,0)$ 开始，目标位于 $(t_x,t_y,0)$ 。如果在任何时候他的高度 $z$ 严格小于 $0 \ (z<0)$ ，则他挑战失败，这意味着他掉进了水里。 在林克的世界里，与地球不同，空气中的物体以 $v_f$ 的恒定速度自由落体。在如此快的坠落速度下，林克无法控制自己的身体，会以零水平速度垂直坠落。幸运的是，林克有滑翔伞来减缓坠落的速度。一旦他打开滑翔伞，下落速度就会变成 $v_p$ ，且 $v_p < v_f$ 。林克能够以最多 $v_h$ 的速度向任何方向水平移动。形式上，link 在 $x$ 方向 $v_x$ ， $y$ 方向上的$v_y$ 速度应满足 $\sqrt{v_x^2+v_y^2} \leq v_h$ 。林克可以多次关闭和打开滑翔伞，而且他可以随时这样做。 对林克来说更好的是，湖里有 $n+1$ 奇怪的风洞，产生向上吹的风，帮助林克飞得更高。这些风穴的编号从 $0$ 到 $n$ ，并由元组$(x_i,y_i,v_i),i="0,1,\dots,n$描述。第" $i$ 个风洞的位置是 $(x_i,y_i,0)$ ，其向上风的速度是 $v_i$ 。林克必须位于垂直线$[ x="x_i,y=y_i]$上，并且他的滑翔伞必须打开才能受到第" 个洞穴的影响。如果林克的滑翔伞在第 个风穴顶部打开，如果 $v_i>v_p$ ，他将以速度 $v_i-v_p$ 上升，如果 $v_p>v_i$ ，他将以速度 $v_p-v_i$ 下降，或者垂直速度为零如果 $v_p=v_i$ 。 Link开始的位置是第 $0$ 个风洞，意思是 $s_x=x_0, s_y=y_0$ 。林克仔细地选择了这个位置，使得 $v_0>v_p$ ，这意味着他最初可以升到他想要的高度。因此，可以证明，只要有足够的时间，林克总能到达目的地而不会掉进湖里。
林克打开和关闭滑翔伞所需的时间以及改变速度所需的时间可以忽略不计。 Link 想知道到达目的地所需的最短时间。

玩塞尔达玩的。
一个简单的dp问题，令dp[i]表示最终在第i个风洞的位置所需要的最短时间，那么可以枚举上一个风洞的位置，从上一个位置转移过来，然后发现好像和在这之前的速度最大的风洞上面多停几秒肯定优于在比它速度小的风洞上停留的时间短。
那么这样就和之前的选择有关联，无法dp。
但是题目对于先去哪个风洞并没有要求，所以直接对风洞的速度大小进行从小到大排序即可，那么从小到大枚举当前风洞，此时的风洞速度一定是目前去过的所有风洞中最大的那个，然后再枚举要去的风洞，因为显然飞到想去的点的位置时林克刚好位于水平面是最不浪费时间的，所以dp[J] = min(dp[J],dp[I] + t + h/v);转移，其中t是过去要花的时间，h/v是最少需要上升h的高度所需要的时间。

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
void solve() {
	int s1, s2, t1, t2;
	cin >> s1 >> s2 >> t1 >> t2;
	int vf, vp, vh;
	cin >> vf >> vp >> vh;
	int n;
	cin >> n;
	vector<array<int, 3>> cave(n + 1);
	for (int i = 0; i <= n; ++i) {
		int x, y, v;
		cin >> x >> y >> v;
		cave[i] = {x, y, v};
	}
	cave.push_back({t1, t2, 0});
	auto getDis = [&](double x1, double y, double x2, double y2) -> double{
		return sqrt((x1 - x2) * (x1 - x2) + (y - y2) * (y - y2));
	};
	vector<vector<double>> dist = vector(n + 2, vector(n + 2, (double)0));
	vector<double> dp(n + 3, (double)1e14);

	for (int i = 0; i <= n + 1; ++i)
		for (int j = 0; j <= n + 1; ++j)
			dist[i][j] = dist[j][i] = getDis(cave[i][0], cave[i][1], cave[j][0], cave[j][1]);
	
	vector<int> p;
	for (int i = 0; i <= n + 1; ++i) p.push_back(i);
	
	sort(p.begin() + 1,p.end() - 1,[&](int a, int b) {
		return cave[a][2] <= cave[b][2];
	});
	dp[0] = 0;
	for (int i = 0; i <= n; ++i) 
		for (int j = i+1; j <= n + 1; ++j) { //这里枚举的时候j从0开始也没问题反正不影响结果
			int I = p[i],J = p[j];
			double v = cave[I][2] - vp;
			if(v > 0){
				double t = dist[I][J]/vh;
				double h = t*vp;
				dp[J] = min(dp[J],dp[I] + t + h/v);
			}
		}
	cout<<dp[n+1]<<endl;
}