QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#291268 | #5458. Shortest Path Query | ngpin04 | TL | 0ms | 3524kb | C++14 | 3.3kb | 2023-12-26 09:47:15 | 2024-06-21 12:38:32 |
Judging History
answer
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define bit(n) (1LL << (n))
#define getbit(x, i) (((x) >> (i)) & 1)
#define pii pair<int, int>
#define ALL(x) x.begin(), x.end()
using namespace std;
const int M = 5e5 + 5;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int oo = 1e9;
const long long ooo = 1e18;
const double pi = acos(-1);
template<typename T1, typename T2> bool mini(T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
typedef long long ll;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("file.inp", "r",stdin);
#endif
int n,m;
cin >> n >> m;
vector <vector <pair <int, int>>> adj(n);
map <pair <int, int>, int> edges;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
if (getbit(edges[mp(u, v)], w))
continue;
edges[{u, v}] |= bit(w);
u--, v--;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int q; cin >> q;
vector <vector <tuple <int, int, int>>> qr(n);
for (int i = 0; i < q; i++) {
int a, b, x;
cin >> a >> b >> x;
x--;
qr[x].push_back({a, b, i});
}
const int mod = 1005;
vector <vector <pair <int, int>>> points(1005);
vector <int> ans(q);
points[0].push_back({0, 0});
auto convex = [&](vector <pair <int, int>> &p) {
vector <pair <int, int>> res;
int sz = 0;
for (auto [x, y] : p) {
while (sz >= 2) {
int a = res[sz - 1].fi - res[sz - 2].fi;
int b = res[sz - 1].se - res[sz - 2].se;
int u = x - res[sz - 2].fi;
int v = y - res[sz - 2].se;
long long prod = (long long) a * v - (long long) b * u;
if (prod <= 0) {
res.pop_back();
sz--;
}
}
res.push_back({x, y});
}
p = res;
};
for (int i = 0; i < n; i++) {
int j = i % mod;
convex(points[j]);
for (auto [a, b, ind] : qr[i]) {
ans[ind] = 2 * oo;
for (auto [x, y] : points[j])
mini(ans[ind], x * a + y * b);
}
for (auto [k, w] : adj[i]) {
int nxt = k % mod;
vector <pair <int, int>> newp;
for (auto [x, y] : points[j]) {
x += (w == 0);
y += (w == 1);
// points[nxt].push_back({x, y});
newp.push_back({x, y});
}
vector <pair <int, int>> newnxt;
for (int i = 0, j = 0; i < (int) points[nxt].size() || j < (int) newp.size();) {
if (i == points[nxt].size() || (j < (int) newp.size() && newp[j] < points[nxt][i]))
newnxt.push_back(newp[j++]);
else
newnxt.push_back(points[nxt][i++]);
}
points[nxt] = newnxt;
convex(points[nxt]);
}
points[j].clear();
}
for (int i = 0; i < q; i++)
cout << ans[i] << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3524kb
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 ...