QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#80343 | #5458. Shortest Path Query | Rainybunny | TL | 3ms | 7880kb | C++14 | 2.8kb | 2023-02-23 14:51:11 | 2023-02-23 14:51:12 |
Judging History
answer
/*+Rainybunny+*/
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)
typedef std::pair<int, int> PII;
#define fi first
#define se second
inline char fgc() {
static char buf[1 << 17], *p = buf, *q = buf;
return p == q && (q = buf + fread(p = buf, 1, 1 << 17, stdin), p == q) ?
EOF : *p++;
}
template <typename Tp = int>
inline Tp rint() {
Tp x = 0, s = fgc(), f = 1;
for (; s < '0' || '9' < s; s = fgc()) f = s == '-' ? -f : f;
for (; '0' <= s && s <= '9'; s = fgc()) x = x * 10 + (s ^ '0');
return x * f;
}
template <typename Tp>
inline void wint(Tp x) {
if (x < 0) putchar('-'), x = -x;
if (9 < x) wint(x / 10);
putchar(x % 10 ^ '0');
}
inline void chkmin(int& u, const int v) { v < u && (u = v, 0); }
const int MAXN = 5e4, IINF = 0x3f3f3f3f;
int n, m, q, qa[MAXN + 5], qb[MAXN + 5], qt[MAXN + 5];
std::vector<PII> adj[MAXN + 5];
namespace Subtask2 {
int dis[MAXN + 5];
inline void main() {
rep (i, 2, n) {
dis[i] = IINF;
for (const PII& e: adj[i]) chkmin(dis[i], dis[e.fi] + 1);
}
rep (i, 1, q) wint(dis[qt[i]] * qa[i]), putchar('\n');
}
} // namespace Subtask2
namespace ShuodeDaoli {
std::map<int, int> dis[MAXN + 5];
inline void init() {
dis[1][0] = 0;
rep (i, 2, n) {
auto touch = [&](const int v)->int& {
auto&& it = dis[i].lower_bound(v);
if (it != dis[i].end() && it->fi == v) return it->se;
else return dis[i].emplace_hint(it, v, IINF)->se;
};
for (const PII& e: adj[i]) {
for (auto&& it = dis[e.fi].begin(); it != dis[e.fi].end(); ++it) {
chkmin(touch(it->fi + !e.se), it->se + e.se);
}
}
for (auto&& it = dis[i].begin(); it != dis[i].end();) {
auto&& nx = std::next(it);
if (nx == dis[i].end()) break;
if (nx->se >= it->se) dis[i].erase(nx);
else it = nx;
}
}
}
inline void main() {
init();
rep (i, 1, q) {
int ans = IINF;
for (auto&& it = dis[qt[i]].begin(); it != dis[qt[i]].end(); ++it) {
chkmin(ans, qa[i] * it->fi + qb[i] * it->se);
}
printf("%d\n", ans);
}
}
} // namespace ShuodeDaoli
int main() {
// freopen("gray.in", "r", stdin);
// freopen("gray.out", "w", stdout);
n = rint(), m = rint();
rep (i, 1, m) {
int u = rint(), v = rint(), c = rint();
adj[v].emplace_back(u, c);
}
q = rint();
rep (i, 1, q) qa[i] = rint(), qb[i] = rint(), qt[i] = rint();
bool proA = true;
rep (i, 1, q) proA &= qa[i] == qb[i];
if (proA) return Subtask2::main(), 0;
ShuodeDaoli::main();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 7880kb
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 ...