結果
問題 |
No.2764 Warp Drive Spacecraft
|
ユーザー |
![]() |
提出日時 | 2024-05-17 22:07:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 361 ms / 3,000 ms |
コード長 | 3,302 bytes |
コンパイル時間 | 2,173 ms |
コンパイル使用メモリ | 210,760 KB |
最終ジャッジ日時 | 2025-02-21 14:52:31 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
コンパイルメッセージ
main.cpp:25:9: warning: #pragma once in main file 25 | #pragma once | ^~~~
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } #define all(x) (x).begin(),(x).end() #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=998244353,MAX=300005; const ll INF=15LL<<58; /** * Author: Simon Lindholm * Date: 2017-04-20 * License: CC0 * Source: own work * Description: Container where you can add lines of the form kx+m, and query maximum values at points x. * Useful for dynamic programming (``convex hull trick''). * Time: O(\log N) * Status: stress-tested */ #pragma once struct Line { mutable ll k, m, p; bool operator<(const Line& o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; struct LineContainerMIN : multiset<Line, less<>> { // (for doubles, use inf = 1/.0, div(a,b) = a/b) static const ll inf = LLONG_MAX; ll div(ll a, ll b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if (y == end()) return x->p = inf, 0; if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(ll k, ll m) { k*=-1;m*=-1; auto z = insert({k, m, 0}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } ll query(ll x) { assert(!empty()); auto l = *lower_bound(x); return -(l.k * x + l.m); } }; ll dis1[MAX],dis2[MAX]; vector<pair<int,ll>> G[MAX]; int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); ll N,M;cin>>N>>M; vector<ll> W(N); for(int i=0;i<N;i++) cin>>W[i]; for(int i=0;i<M;i++){ ll a,b,c;cin>>a>>b>>c;a--;b--; G[a].push_back(mp(b,c)); G[b].push_back(mp(a,c)); } for(int i=0;i<N;i++){ dis1[i]=INF; dis2[i]=INF; } { dis1[0]=0; priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> PQ; PQ.push(mp(0,0)); while(!PQ.empty()){ auto [d,u]=PQ.top();PQ.pop(); if(dis1[u]<d) continue; for(auto [to,co]:G[u]){ if(chmin(dis1[to],dis1[u]+co)) PQ.push(mp(dis1[to],to)); } } } { dis2[N-1]=0; priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> PQ; PQ.push(mp(0,N-1)); while(!PQ.empty()){ auto [d,u]=PQ.top();PQ.pop(); if(dis2[u]<d) continue; for(auto [to,co]:G[u]){ if(chmin(dis2[to],dis2[u]+co)) PQ.push(mp(dis2[to],to)); } } } ll ans=dis1[N-1]; LineContainerMIN cht; for(int i=0;i<N;i++){ cht.add(W[i],dis2[i]); } for(int i=0;i<N;i++){ chmin(ans,cht.query(W[i])+dis1[i]); } cout<<ans<<endl; }