QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#168350 | #5458. Shortest Path Query | syksykCCC | TL | 1ms | 4972kb | C++14 | 2.1kb | 2023-09-08 10:54:38 | 2024-06-21 12:38:12 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<pair<int, int>> vpii;
const int N = 5e4 + 5, M = 1e5 + 5, R = 1001;
vpii G[N], conv[R]; // (w = 0, w = 1)
struct query { ll u, a, b, id, ans; } Q[N];
int n, m, q;
void add(vpii &c, int x, int y) {
if(c.empty()) { c.emplace_back(x, y); return; }
if(c.back().second <= 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);
}
vpii merge(const vpii &A, const vpii &B, int dx, int dy) {
int i = 0, j = 0;
vpii 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;
}
}
assert(cur == q + 1);
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: 4972kb
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 ...