QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168153#5458. Shortest Path QuerysyksykCCCTL 1ms6088kbC++142.1kb2023-09-07 22:24:112024-06-21 12:38:12

Judging History

你现在查看的是最新测评结果

  • [2024-06-21 12:38:12]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:1ms
  • 内存:6088kb
  • [2023-09-07 22:24:11]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:6648kb
  • [2023-09-07 22:24:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 5, M = 1e5 + 5, R = 1001;
vector<pair<int, int>> G[N], conv[R]; // (w = 0, w = 1)
struct query { ll u, a, b, id, ans; } Q[N]; 
int n, m, q;
void add(vector<pair<int, int>> &c, int x, int y) {
	if(c.empty()) { c.emplace_back(x, y); return; }
	if(c.back().first == x)	y = min(c.back().second, y), c.pop_back();
	while(c.size() > 1) {
		int e = (int)c.size() - 1;
		if((ll)(c[e-1].second - c[e].second) * (c[e].first - x) 
			< (ll)(c[e-1].second - y) * (c[e-1].first - c[e].first)) c.pop_back();
		else break;
	}
	c.emplace_back(x, y);
}
vector<pair<int, int>> merge(const vector<pair<int, int>> &A, const vector<pair<int, int>> &B, int dx, int dy) {
	int i = 0, j = 0;
	vector<pair<int, int>> res;
	while(i < A.size() && j < B.size()) {
		if(A[i].first <= B[i].first + dx) add(res, A[i].first, A[i].second), i++;
		else add(res, B[j].first + dx, B[j].second + dy), j++;
	}
	for(; i < A.size(); i++) add(res, A[i].first, A[i].second);
	for(; j < B.size(); j++) add(res, B[j].first + dx, B[j].second + dy);
	return res;
}
int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		G[v].emplace_back(u, c); // reversed edge
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; i++) {
		scanf("%lld %lld %lld", &Q[i].a, &Q[i].b, &Q[i].u);
		Q[i].id = i;
	}
	sort(Q + 1, Q + q + 1, [&](const query &A, const query &B){ return A.u < B.u; });
	conv[1].emplace_back(0, 0);
	int cur = 1;
	for(int u = 1; u <= n; u++) {
		if(u >= R) conv[u % R].clear();
		for(auto e : G[u]) {
			int v = e.first, w = e.second;
			conv[u % R] = merge(conv[u % R], conv[v % R], w == 0, w == 1);
		}
		while(cur <= q && Q[cur].u == u) {
			ll ans = LLONG_MAX;
			for(auto p : conv[u % R]) {
				ans = min(ans, p.first * Q[cur].a + p.second * Q[cur].b);
			}
			Q[cur++].ans = ans;
		}
	}
	sort(Q + 1, Q + q + 1, [&](const query &A, const query &B){ return A.id < B.id; });
	for(int i = 1; i <= q; i++) printf("%lld\n", Q[i].ans);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 6088kb

input:

4 4
1 2 0
1 3 1
2 4 0
3 4 1
3
3 5 2
3 2 4
2 3 4

output:

3
4
4

result:

ok 3 number(s): "3 4 4"

Test #2:

score: -100
Time Limit Exceeded

input:

50000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 9 1
9 10 0
10 11 1
11 12 1
12 13 1
13 14 0
14 15 0
15 16 0
16 17 0
17 18 1
18 19 1
19 20 0
20 21 1
21 22 0
22 23 0
23 24 1
24 25 1
25 26 0
26 27 1
27 28 0
28 29 0
29 30 0
30 31 0
31 32 1
32 33 0
33 34 1
34 35 1
35 36 1
36 37 1
37 38 0
38 39 0
...

output:


result: