結果
問題 | No.2764 Warp Drive Spacecraft |
ユーザー |
👑 |
提出日時 | 2024-04-29 10:57:11 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 691 ms / 3,000 ms |
コード長 | 3,222 bytes |
コンパイル時間 | 3,196 ms |
コンパイル使用メモリ | 241,684 KB |
実行使用メモリ | 36,140 KB |
最終ジャッジ日時 | 2024-05-18 00:09:31 |
合計ジャッジ時間 | 16,582 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 3 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 3 ms
6,944 KB |
testcase_13 | AC | 3 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 320 ms
36,140 KB |
testcase_17 | AC | 319 ms
35,592 KB |
testcase_18 | AC | 311 ms
35,308 KB |
testcase_19 | AC | 515 ms
24,036 KB |
testcase_20 | AC | 517 ms
25,352 KB |
testcase_21 | AC | 521 ms
24,596 KB |
testcase_22 | AC | 515 ms
24,420 KB |
testcase_23 | AC | 516 ms
25,740 KB |
testcase_24 | AC | 515 ms
24,472 KB |
testcase_25 | AC | 522 ms
26,104 KB |
testcase_26 | AC | 674 ms
33,672 KB |
testcase_27 | AC | 647 ms
34,268 KB |
testcase_28 | AC | 665 ms
34,408 KB |
testcase_29 | AC | 691 ms
34,976 KB |
testcase_30 | AC | 662 ms
33,596 KB |
testcase_31 | AC | 670 ms
35,344 KB |
testcase_32 | AC | 673 ms
35,512 KB |
testcase_33 | AC | 367 ms
22,168 KB |
testcase_34 | AC | 367 ms
23,492 KB |
testcase_35 | AC | 375 ms
21,028 KB |
testcase_36 | AC | 317 ms
35,552 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; template<typename T> void chmin(T& a, T b){a = min(a, b);} // thanks for Luzhiled's memo // https://ei1333.github.io/luzhiled/snippets/dp/monotone-minima.html template<typename T, typename Compare = less<T>> pair<vector<int>, vector<T>> monotone_minima(int H, int W, const function<T(int, int)> &f, const Compare &comp = Compare()) { vector<int> idx(H); vector<T> res(H); function<void(int, int, int, int)> dfs = [&](int top, int bottom, int left, int right) { if(top > bottom) return; int line = (top + bottom) / 2; T ma = 0; int mi = -1; for(int i = left; i <= right; i++) { T cst = f(line, i); if(mi == -1 || comp(cst, ma)) { ma = cst; mi = i; } } idx[line] = mi; res[line] = ma; dfs(top, line - 1, left, mi); dfs(line + 1, bottom, mi, right); }; dfs(0, H - 1, 0, W - 1); return make_pair(idx, res); } const long long INF = 2002002002002002002; using S = long long; S _INF(INF); S _ZERO(0LL); using F = long long; S apply(F f, S x){ return f + x; } template<typename S, typename F> struct Dijkstra{ struct Edge{ int from, to; F cost; Edge(int from, int to, F cost) : from(from), to(to), cost(cost) {}; }; int n, m; vector<bool> initialized; vector<Edge> E; vector<vector<int>> G; map<int, vector<S>> dist; map<int, vector<int>> idx; Dijkstra(int _n) : n(_n), m(0), initialized(n, false), G(n){} void add_edge(int from, int to, F cost){ Edge e(from, to, cost); E.push_back(e); G[from].emplace_back(m); m++; } void calc(int s){ initialized[s] = true; dist[s] = vector<S>(n, _INF); idx[s] = vector<int>(n, -1); priority_queue<tuple<S, int, int>, vector<tuple<S, int, int>>, greater<tuple<S, int, int>>> pq; pq.emplace(_ZERO, s, -1); while(pq.size()){ auto [dist_from, from, index] = pq.top(); pq.pop(); if(dist[s][from] <= dist_from) continue; dist[s][from] = dist_from; idx[s][from] = index; for(int index : G[from]){ int to = E[index].to; S dist_to = apply(E[index].cost, dist_from); if(dist[s][to] <= dist_to) continue; pq.emplace(dist_to, to, index); } } } S get_dist(int s, int t){ if(!initialized[s]) calc(s); return dist[s][t]; } }; int main(){ int n, m; cin >> n >> m; vector<long long> w(n); for(int i = 0; i < n; i++) cin >> w[i]; Dijkstra<long long, long long> graph(n); for(int i = 0; i < m; i++){ int u, v; long long t; cin >> u >> v >> t; u--; v--; graph.add_edge(u, v, t); graph.add_edge(v, u, t); } vector<long long> dist_s(n); vector<long long> dist_t(n); for(int i = 0; i < n; i++) dist_s[i] = graph.get_dist(0, i); for(int i = 0; i < n; i++) dist_t[i] = graph.get_dist(n - 1, i); long long ans = dist_s[n - 1]; vector<int> asc(n); for(int i = 0; i < n; i++) asc[i] = i; sort(asc.begin(), asc.end(), [&](int left, int right){ return w[left] < w[right]; }); // W_pi * W_pj + dist(pj, N) // W[p1] <= W[p2] <= ... <= W[pN] function<long long(int, int)> f = [&](int i, int j){ return w[asc[i]] * w[asc[(n - 1) - j]] + dist_t[asc[(n - 1) - j]]; }; auto [idx, val] = monotone_minima(n, n, f); for(int i = 0; i < n; i++){ chmin(ans, dist_s[asc[i]] + val[i]); } cout << ans << "\n"; return 0; }