QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#75491 | #5458. Shortest Path Query | JooDdae | TL | 0ms | 6944kb | C++14 | 1.4kb | 2023-02-05 14:09:02 | 2023-02-05 14:09:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, q, ans[50050];
vector<array<int, 2>> v[50050], c[50050];
vector<array<int, 3>> Q[50050];
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for(int i=1;i<=m;i++) {
int a, b, c; cin >> a >> b >> c;
v[b].push_back({a, c});
}
cin >> q;
for(int i=1;i<=q;i++) {
int a, b, c; cin >> a >> b >> c;
Q[c].push_back({a, b, i});
}
c[1].push_back({0, 0});
for(int i=1;i<=n;i++) {
c[i].push_back({n, n});
for(auto [x, y] : v[i]) {
vector<array<int, 2>> C;
int j = 0, k = 0;
while(j < c[i].size() || k < c[x].size()) {
if(k == c[x].size() || (j < c[i].size() && c[i][j][0] >= c[x][k][0]+!y)) {
auto [X, Y] = c[i][j++];
C.push_back({X, Y});
} else {
auto [X, Y] = c[x][k++];
(y ? Y : X) += 1;
C.push_back({X, Y});
}
}
c[i] = C;
}
for(auto [a, b, id] : Q[i]) {
ans[id] = INT_MAX;
for(auto [x, y] : c[i]) ans[id] = min(ans[id], a*x + b*y);
}
if(i > 1000) c[i-1000].clear();
}
for(int i=1;i<=q;i++) cout << ans[i] << "\n";
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6944kb
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
Memory 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 ...