QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#107988 | #5458. Shortest Path Query | xcyle | WA | 65ms | 15772kb | C++14 | 1.9kb | 2023-05-23 13:08:23 | 2023-05-23 13:08:25 |
Judging History
answer
/*
_/ _/ _/_/_/ _/ _/ _/ _/_/_/_/_/
_/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/
_/_/ _/ _/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/
_/ _/ _/_/_/ _/ _/_/_/_/_/ _/_/_/_/_/
*/
#include <bits/stdc++.h>
#define ll long long
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ru(i, l, r) for (int i = (l); i <= (r); i++)
#define rd(i, r, l) for (int i = (r); i >= (l); i--)
#define mid ((l + r) >> 1)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define sz(s) (int)s.size()
#define maxn 50005
using namespace std;
int read() {
int x = 0, w = 0; char ch = getchar();
while(!isdigit(ch)) w |= ch == '-', ch = getchar();
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return w ? -x : x;
}
int n, m;
vector<pii> G[maxn], pt[maxn];
int chk(pii a, pii b, pii c) {
return (ll)(b.fi - a.fi) * (c.se - b.se) >= (ll)(b.se - a.se) * (c.fi - b.fi);
}
int main() {
n = read(), m = read();
ru(i, 1, m) {
int x = read(), y = read(), c = read();
G[x].push_back(mp(y, c));
}
pt[1].push_back(mp(0, 0));
ru(i, 1, n) {
vector<pii> tmp = pt[i]; pt[i].clear();
sort(tmp.begin(), tmp.end());
for (auto x: tmp) {
while(pt[i].size() > 2 && chk(pt[i][pt[i].size() - 2], pt[i].back(), x)) pt[i].pop_back();
pt[i].push_back(x);
}
for (auto V: G[i]) for (auto x: pt[i]) {
pt[V.fi].push_back(mp(x.fi + 1 - V.se, x.se + V.se));
}
}
int q = read();
while(q--) {
int a = read(), b = read(), i = read(); ll ans = 1e18;
for (auto x: pt[i]) ans = min(ans, (ll)a * x.fi + (ll)b * x.se);
printf("%lld\n", ans);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5868kb
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
Wrong Answer
time: 65ms
memory: 15772kb
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:
171090050 250459598 258589143 259699419 104338880 16685198 59196446 64713954 46949896 245672377 94777502 84753103 267419449 192242757 216482422 147454419 111021650 80187604 247374700 111782626 121405290 249524638 191332392 202049239 343798460 173714177 174899498 97998224 96431009 280559577 164349486...
result:
wrong answer 1st numbers differ - expected: '164602050', found: '171090050'