結果
| 問題 | No.2764 Warp Drive Spacecraft |
| ユーザー |
 drken1215
|
| 提出日時 | 2026-11-13 12:38:53 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 19,060 bytes |
| 記録 | |
| コンパイル時間 | 3,460 ms |
| コンパイル使用メモリ | 372,448 KB |
| 実行使用メモリ | 31,716 KB |
| 最終ジャッジ日時 | 2026-11-13 12:39:51 |
| 合計ジャッジ時間 | 15,900 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge5_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 19 WA * 20 |
ソースコード
#line 1 "test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/2546"
#include <bits/stdc++.h>
using namespace std;
#line 4 "https://drken1215.github.io/algorithm/template.hpp.html"
using namespace std;
// My library is in https://github.com/drken1215/algorithm
#line 4 "https://drken1215.github.io/algorithm/Others/macro.hpp.html"
using namespace std;
using ll = long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pint = pair<int, int>;
using pll = pair<long long, long long>;
using tll = array<long long, 3>;
using fll = array<long long, 4>;
using vint = vector<int>;
using vll = vector<long long>;
using dint = deque<int>;
using dll = deque<long long>;
using vvint = vector<vector<int>>;
using vvll = vector<vector<long long>>;
using vpll = vector<pair<long long, long long>>;
template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<class S, class T> inline bool chmax(S &a, T b) { return (a < b ? a = b, 1 : 0); }
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }
template<class S, class T> inline auto maxll(S a, T b) { return max(ll(a), ll(b)); }
template<class S, class T> inline auto minll(S a, T b) { return min(ll(a), ll(b)); }
template<class T> auto max(const T &a) { return *max_element(a.begin(), a.end()); }
template<class T> auto min(const T &a) { return *min_element(a.begin(), a.end()); }
template<class T> auto argmax(const T &a) { return max_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto argmin(const T &a) { return min_element(a.begin(), a.end()) - a.begin(); }
template<class T> auto accum(const vector<T> &a) { return accumulate(a.begin(), a.end(), T()); }
template<class T> auto accum(const deque<T> &a) { return accumulate(a.begin(), a.end(), T()); }
#define REP(i, a) for (long long i = 0; i < (long long)(a); i++)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); i++)
#define RREP(i, a) for (long long i = (a)-1; i >= (long long)(0); --i)
#define RREP2(i, a, b) for (long long i = (b)-1; i >= (long long)(a); --i)
#define EB emplace_back
#define PF push_front
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(x) x.begin(), x.end()
#line 3 "https://drken1215.github.io/algorithm/Others/stl_container_stream.hpp.html"
using namespace std;
// input stream
template<class T> istream& operator >> (istream &is, vector<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, deque<T> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
template<class T> istream& operator >> (istream &is, vector<vector<T>> &P)
{ for (int i = 0; i < (int)P.size(); ++i) cin >> P[i]; return is; }
// output stream
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class S, class T> ostream& operator << (ostream &s, const pair<S, T> &P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 2> &P)
{ return s << '<' << P[0] << "," << P[1] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 3> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << '>'; }
template<class T> ostream& operator << (ostream &s, const array<T, 4> &P)
{ return s << '<' << P[0] << "," << P[1] << "," << P[2] << "," << P[3] << '>'; }
template<class T> ostream& operator << (ostream &s, const vector<string> &P)
{ for (int i = 0; i < P.size(); ++i) { s << P[i] << endl; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const deque<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, const vector<vector<T>> &P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, const set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const multiset<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class T> ostream& operator << (ostream &s, const unordered_set<T> &P)
{ for (auto it : P) { s << "<" << it << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
template<class S, class T> ostream& operator << (ostream &s, const unordered_map<S, T> &P)
{ for (auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
// Yes/No
void yes(bool a) { cout << (a ? "yes" : "no") << endl; }
void YES(bool a) { cout << (a ? "YES" : "NO") << endl; }
void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; }
#line 4 "https://drken1215.github.io/algorithm/Graph/graph.hpp.html"
using namespace std;
// Edge Class
template<class T = long long> struct Edge {
int from, to;
T val;
Edge() : from(-1), to(-1) { }
Edge(int f, int t, T v = 1) : from(f), to(t), val(v) {}
Edge(const Edge&) = default;
Edge& operator = (const Edge&) = default;
friend ostream& operator << (ostream& s, const Edge& e) {
return s << e.from << "->" << e.to << "(" << e.val << ")";
}
};
// graph class
template<class T = long long> struct Graph {
int V;
bool record_reversed_edges = false, record_edge_index = false;
vector<vector<Edge<T>>> list;
vector<vector<Edge<T>>> reversed_list;
vector<unordered_map<int, int>> id; // id[v][w] := the index of node w in G[v]
// constructors
Graph(int n = 0, bool rre = false, bool rei = false) {
init(n, rre, rei);
}
void init(int n = 0, bool rre = false, bool rei = false) {
V = n, record_reversed_edges = rre, record_edge_index = rei;
list.assign(n, vector<Edge<T>>());
if (record_reversed_edges) reversed_list.assign(n, vector<Edge<T>>());
if (record_edge_index) id.assign(n, unordered_map<int, int>());
}
Graph(const Graph&) = default;
Graph& operator = (const Graph&) = default;
// getters
vector<Edge<T>> &operator [] (int i) { return list[i]; }
const vector<Edge<T>> &operator [] (int i) const { return list[i]; }
constexpr size_t size() const { return list.size(); }
constexpr void clear() { V = 0; list.clear(); }
constexpr void resize(int n) { V = n; list.resize(n); }
const vector<Edge<T>> &get_rev_edges(int i) const {
assert(record_reversed_edges);
return reversed_list[i];
}
Edge<T> &get_edge(int u, int v) {
assert(record_edge_index);
assert(u >= 0 && u < list.size() && v >= 0 && v < list.size());
assert(id[u].count(v) && id[u][v] >= 0 && id[u][v] < list[u].size());
return list[u][id[u][v]];
}
const Edge<T> &get_edge(int u, int v) const {
assert(record_edge_index);
assert(u >= 0 && u < list.size() && v >= 0 && v < list.size());
assert(id[u].count(v) && id[u].at(v) >= 0 && id[u].at(v) < list[u].size());
return list[u][id[u].at(v)];
}
// add edge
void add_edge(int from, int to, T val = 1) {
assert(0 <= from && from < list.size() && 0 <= to && to < list.size());
if (record_edge_index) id[from][to] = (int)list[from].size();
list[from].push_back(Edge(from, to, val));
if (record_reversed_edges) reversed_list[to].push_back(Edge(to, from, val));
}
void add_bidirected_edge(int from, int to, T val = 1) {
assert(0 <= from && from < list.size() && 0 <= to && to < list.size());
if (record_edge_index) id[from][to] = (int)list[from].size();
list[from].push_back(Edge(from, to, val));
if (record_reversed_edges) reversed_list[to].push_back(Edge(to, from, val));
if (from != to) {
if (record_edge_index) id[to][from] = (int)list[to].size();
list[to].push_back(Edge(to, from, val));
if (record_reversed_edges) reversed_list[from].push_back(Edge(from, to, val));
}
}
// input (only tree-case)
friend istream& operator >> (istream &is, Graph &G) {
for (int i = 0; i < G.V - 1; i++) {
int u, v;
is >> u >> v, u--, v--;
G.add_bidirected_edge(u, v);
}
return is;
}
// output
friend ostream &operator << (ostream &os, const Graph &G) {
os << endl;
for (int i = 0; i < (int)G.size(); ++i) {
os << i << " -> ";
for (int j = 0; j < (int)G[i].size(); j++) {
if (j) os << ", ";
os << G[i][j].to << "(" << G[i][j].val << ")";
}
os << endl;
}
return os;
}
};
#line 4 "https://drken1215.github.io/algorithm/Optimization/general_li_chao_tree.hpp.html"
using namespace std;
// General Li-Chao Tree (Dynamic ver.) for Pairwise Single Crossing Functions
template<class VAL, class FUNC, class X = long long> struct DynamicGeneralLiChaoTree {
struct Node {
int id = -1; // function id
Node *left = nullptr, *right = nullptr;
};
// inner values using chunk-based memory pool
vector<unique_ptr<Node[]>> blocks;
vector<FUNC> funcs;
Node *root = nullptr;
X XL, XR;
VAL INF = numeric_limits<VAL>::max() / 2;
// constructors
explicit DynamicGeneralLiChaoTree(X xl, X xr, VAL inf = numeric_limits<VAL>::max() / 2)
: XL(xl), XR(xr), INF(inf) {
assert(xl < xr);
}
// basic functions
void reserve_functions(size_t n) {
funcs.reserve(n);
}
VAL eval(int id, X x) const {
return funcs[id](x);
}
bool better(int fid, int gid, X x) const {
VAL a = eval(fid, x), b = eval(gid, x);
return (a < b) || (a == b && fid < gid);
}
void clear() {
funcs.clear();
blocks.clear();
used = BLOCK;
root = nullptr;
}
// insert(f), in O(log X)
int insert(FUNC f) {
int id = (int)funcs.size();
funcs.push_back(std::move(f));
insert_at(root, XL, XR, id);
return id;
}
// insert_segment(l, r, f), in O(log^2 X)
int insert_segment(FUNC f, X l, X r) {
assert(XL <= l && l <= r && r <= XR);
int id = (int)funcs.size();
funcs.push_back(std::move(f));
if (l != r) insert_segment_at(root, XL, XR, l, r, id);
return id;
}
// query(x), in O(log X)
pair<VAL, int> query(X x) const {
assert(XL <= x && x < XR);
VAL best = INF;
int best_id = -1;
Node *p = root;
X left = XL, right = XR;
while (p) {
if (p->id != -1) {
int fid = p->id;
VAL y = eval(fid, x);
if (best_id == -1 || y < best || (y == best && fid < best_id)) {
best = y, best_id = fid;
}
}
if (right - left == 1) break;
X mid = (left + right) / 2;
if (x < mid) p = p->left, right = mid;
else p = p->right, left = mid;
}
return {best, best_id};
}
private:
// chunk-based node allocation
static constexpr int BLOCK = 4096;
int used = BLOCK;
Node *new_node() {
if (used == BLOCK) {
blocks.emplace_back(make_unique<Node[]>(BLOCK));
used = 0;
}
return &blocks.back()[used++];
}
// inner insert
void insert_at(Node *&p, X left, X right, int fid) {
Node **cur = &p;
while (true) {
if (!*cur) *cur = new_node();
Node *v = *cur;
int gid = v->id;
if (gid == -1) {
v->id = fid;
return;
}
bool left_better = better(fid, gid, left), right_better = better(fid, gid, right - 1);
if (!left_better && !right_better) return;
if (left_better && right_better) {
v->id = fid;
return;
}
X mid = (left + right) / 2;
bool mid_better = better(fid, gid, mid);
if (mid_better) v->id = fid, fid = gid;
if (left_better != mid_better) cur = &v->left, right = mid;
else cur = &v->right, left = mid;
}
}
// inner insert_segment
void insert_segment_at(Node *&p, X left, X right, X l, X r, int fid) {
if (r <= left || right <= l) return;
if (l <= left && right <= r) {
insert_at(p, left, right, fid);
return;
}
if (!p) p = new_node();
X mid = (left + right) / 2;
if (l < mid) insert_segment_at(p->left, left, mid, l, r, fid);
if (mid < r) insert_segment_at(p->right, mid, right, l, r, fid);
}
};
// General Li-Chao Tree (Coordinate Compression ver.) for Pairwise Single Crossing Functions
template<class VAL, class FUNC, class X = long long> struct GeneralLiChaoTree {
// inner values
int N, XL, SIZ;
bool compressed = true;
VAL INF = numeric_limits<VAL>::max() / 2;
vector<X> xs;
vector<int> ids;
vector<FUNC> funcs;
// constructors
explicit GeneralLiChaoTree(vector<X> xs_, VAL inf = numeric_limits<VAL>::max() / 2, bool sorted = true)
: N((int)xs_.size()), XL(0), SIZ(1), compressed(true), INF(inf), xs(std::move(xs_)) {
if (!sorted) {
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
}
while (SIZ < N) SIZ <<= 1;
ids.assign(SIZ << 1, -1);
}
explicit GeneralLiChaoTree(int xl, int xr, VAL inf = numeric_limits<VAL>::max() / 2)
: N(xr - xl), XL(xl), SIZ(1), compressed(false), INF(inf) {
assert(N >= 0);
while (SIZ < N) SIZ <<= 1;
ids.assign(SIZ << 1, -1);
}
// basic functions
void reserve_functions(size_t n) {
funcs.reserve(n);
}
VAL eval(int id, X x) const {
return funcs[id](x);
}
bool better(int fid, int gid, X x) const {
VAL a = eval(fid, x), b = eval(gid, x);
return (a < b) || (a == b && fid < gid);
}
void clear() {
funcs.clear();
fill(ids.begin(), ids.end(), -1);
}
// insert(f), in O(log N)
int insert(FUNC f) {
int id = (int)funcs.size();
funcs.push_back(std::move(f));
if (N) insert_at(1, 0, SIZ, id);
return id;
}
// insert_segment(f, l, r), in O(log^2 N)
int insert_segment(FUNC f, X l, X r) {
assert(l <= r);
int id = (int)funcs.size();
funcs.push_back(std::move(f));
if (N == 0 || l == r) return id;
int L = lower_bound_index(l);
int R = lower_bound_index(r);
if (L == R) return id;
int a = L + SIZ, b = R + SIZ;
while (a < b) {
if (a & 1) {
int v = a++;
int depth = 31 - __builtin_clz((unsigned)v);
int length = SIZ >> depth;
int left = (v - (1 << depth)) * length;
insert_at(v, left, left + length, id);
}
if (b & 1) {
int v = --b;
int depth = 31 - __builtin_clz((unsigned)v);
int length = SIZ >> depth;
int left = (v - (1 << depth)) * length;
insert_at(v, left, left + length, id);
}
a >>= 1, b >>= 1;
}
return id;
}
// query(x), x must be in xs, in O(log N)
pair<VAL, int> query(X x) const {
int pos = 0;
if (compressed) {
auto it = lower_bound(xs.begin(), xs.end(), x);
assert(it != xs.end() && *it == x);
pos = int(it - xs.begin());
} else {
assert(X(XL) <= x && x < X(XL + N));
pos = int(x - XL);
}
VAL best = INF;
int best_id = -1;
int v = pos + SIZ;
while (v) {
int fid = ids[v];
if (fid != -1) {
VAL y = eval(fid, x);
if (best_id == -1 || y < best || (y == best && fid < best_id)) {
best = y, best_id = fid;
}
}
v >>= 1;
}
return {best, best_id};
}
private:
// coordinate compression
int lower_bound_index(X x) const {
if (compressed) {
return int(std::lower_bound(xs.begin(), xs.end(), x) - xs.begin());
} else {
if (x <= X(XL)) return 0;
else if (x >= X(XL) + X(N)) return N;
else return int(x - X(XL));
}
}
// inner insert
void insert_at(int v, int left, int right, int fid) {
auto coord = [&](int i) -> X {
i = min(i, N - 1);
return (compressed ? xs[i] : X(i) + X(XL));
};
while (true) {
int gid = ids[v];
if (gid == -1) {
ids[v] = fid;
return;
}
bool left_better = better(fid, gid, coord(left));
bool right_better = better(fid, gid, coord(right - 1));
if (!left_better && !right_better) return;
if (left_better && right_better) {
ids[v] = fid;
return;
}
X mid = (left + right) / 2;
bool mid_better = better(fid, gid, coord(mid));
if (mid_better) ids[v] = fid, fid = gid;
if (left_better != mid_better) {
v <<= 1;
right = mid;
} else {
v = v << 1 | 1;
left = mid;
}
}
}
};
#line 9 "test.cpp"
int main() {
ll N, M, MAX = 1LL << 31, INF = 1LL << 61;
cin >> N >> M;
vll W(N);
cin >> W;
Graph<ll> G(N);
REP(i, M) {
ll u, v, w;
cin >> u >> v >> w, u--, v--;
G.add_edge(u, v, w);
}
auto dijkstra = [&](vll &dp) {
min_priority_queue<pll> que;
for (int v = 0; v < N; v++) que.push({dp[v], v});
while (!que.empty()) {
auto [cur, v] = que.top(); que.pop();
if (cur > dp[v]) continue;
for (auto e : G[v]) {
if (chmin(dp[e.to], dp[v] + e.val)) {
que.push({dp[e.to], e.to});
}
}
}
};
vll dp(N, INF), dp2(N, INF);
dp[0] = 0;
dijkstra(dp);
auto make_func = [&](ll a, ll b) {
return [&, a, b](ll x) -> ll {
return a * x + b;
};
};
DynamicGeneralLiChaoTree<ll, decltype(make_func(0, 0))> cht(0, MAX);
for (int v = 0; v < N; v++) cht.insert(make_func(W[v], dp[v]));
for (int v = 0; v < N; v++) {
chmin(dp2[v], cht.query(W[v]).first);
}
dijkstra(dp2);
ll res = min(dp[N-1], dp2[N-1]);
cout << res << endl;
}