【SSL 1455】不稳定的道路（最短路）

不稳定的道路

题目链接：SSL 1455

题目大意

一个无向图，你在 i 时刻通过某一条边 x，需要的时间是 c[x]+d[x]/i（除要下取整），然后问你从 1 到 n 的最短时间。
可以在一个点等待。

思路

发现能等，那还是能早到就早到。

那你考虑走怎样的一个时机，看着就是先变优再变劣的。
（千万不要用三分，因为可能权值会有一样的，会去世的）

不过你可以理解为一个是 $x$ 一个是 $d/x$，那大概是取在 $\sqrt{d}$ 的位置。（准确来说是 $\max (\sqrt{d},s)$，即要跟你现在的时间大或者一样，因为你不能等负数的时间）

那不一定是刚好这个位置，就可能有点修正之类的，随便来个 $\pm 3$ 都能过了。

代码

#include
#include
#include
#include
#include
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

const ll N = 1e5 + 100;
struct node {
	ll a, b, to, nxt;
}e[N << 1];
ll n, m, le[N], KK;
ll f[N];
priority_queue <pair<ll, ll>, vector<pair<ll, ll> >, greater<pair<ll, ll> > > q;
bool in[N];

void add(ll x, ll y, ll a, ll b) {
	e[++KK] = (node){a, b, y, le[x]}; le[x] = KK;
}

ll get(ll t, ll a, ll b) {
	return t + a + b / (t + 1);
}

int main() {
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout); 
	
	scanf("%lld %lld", &n, &m);
	for (ll i = 1; i <= m; i++) {
		ll a, b, c, d; scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
		add(a, b, c, d); add(b, a, c, d);
	}
	
	memset(f, 0x7f, sizeof(f)); f[1] = 0; q.push(make_pair(f[1], 1));
	while (!q.empty()) {
		ll now = q.top().second; q.pop(); if (in[now]) continue; in[now] = 1;
		for (ll i = le[now]; i; i = e[i].nxt) {
			if (in[e[i].to]) continue;
			ll x = 1e18;
			ll L = max(f[now], (ll)sqrt(e[i].b) - 3), R = max(f[now], (ll)sqrt(e[i].b) + 3);
			for (ll j = L; j <= R; j++) x = min(x, get(j, e[i].a, e[i].b));
			if (f[e[i].to] > x) {
				f[e[i].to] = x; q.push(make_pair(f[e[i].to], e[i].to));
			}
		}
	}
	
	if (f[n] == f[0]) printf("-1");
		else printf("%lld", f[n]);
	
	return 0;
}
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