結果
| 問題 | No.1995 CHIKA Road |
| ユーザー |
 log_K
|
| 提出日時 | 2023-06-26 10:57:49 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 448 ms / 2,000 ms |
| コード長 | 13,216 bytes |
| コンパイル時間 | 2,834 ms |
| コンパイル使用メモリ | 223,524 KB |
| 最終ジャッジ日時 | 2025-02-15 02:22:16 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
#line 2 "library/Template.hpp"/*** @brief Procon Template - テンプレート*/#include <bits/stdc++.h>#define ALL(x) (x).begin(), (x).end()#define RALL(x) (x).rbegin(), (x).rend()#define SORT(x) sort(ALL(x))#define RSORT(x) sort(RALL(x))#define REV(x) reverse(ALL(x))#define SETPRE(digit) fixed << setprecision(digit)#define popcount(x) __builtin_popcount(x)#define ACC(x) accumulate((x).begin(), (x).end(), 0LL)using namespace std;inline string Yn(bool flag){return (flag) ? "Yes" : "No";}inline bool YnPrint(bool flag){cout << Yn(flag) << endl;return flag;}inline string YN(bool flag){return (flag) ? "YES" : "NO";}inline bool YNPrint(bool flag){cout << YN(flag) << endl;return flag;}template<class T>bool minin(T &src, const T &cmp){if(src > cmp){src = cmp; return true;}return false;}template<class T>bool maxin(T &src, const T &cmp){if(src < cmp){src = cmp; return true;}return false;}template<typename T>inline bool between(T min, T x, T max){return min <= x && x <= max;}template<typename T>inline T median(T a, T b, T c){return between(b, a, c) || between(c, a, b) ? a : (between(a, b, c) || between(c, b, a) ? b : c);}using ll = long long;using ull = unsigned long long;const double PI = 3.141592653589793;const double PI2 = PI * 2;const double PI_2 = PI / 2;const int INF_INT = numeric_limits<int>::max() / 2;const long long INF_LL = numeric_limits<long long>::max() / 2LL;template <typename T>using vec = vector<T>;using pi = pair<int, int>;using pll = pair<ll, ll>;using pd = pair<double, double>;template <typename T>using pq = priority_queue<T>;template <typename T>using rpq = priority_queue<T, vec<T>, greater<T>>;const int dx4[4] = {1, 0, -1, 0};const int dy4[4] = {0, -1, 0, 1};const int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};const int dy8[8] = {0, -1, -1, -1, 0, 1, 1, 1};template <typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << "{" << p.first << " " << p.second << "}";return os;}template <typename T1, typename T2>istream &operator>>(istream &is, pair<T1, T2> &p){is >> p.first >> p.second;return is;}template <typename T>ostream &operator<<(ostream &os, vector<T> &v){for (int i = 0; i < v.size(); ++i){os << v[i] << (i + 1 != v.size() ? " " : "");}return os;}template <typename T>ostream &operator<<(ostream &os, vector<vector<T>> &v){for (int i = 0; i < v.size(); ++i){os << v[i] << "\n";}return os;}template <typename T>istream &operator>>(istream &is, vector<T> &v){for (int i = 0; i < v.size(); ++i) is >> v[i];return is;}template <typename T>istream &operator>>(istream &is, valarray<T> &v){for (int i = 0; i < v.size(); ++i) is >> v[i];return is;}template <typename T1, typename T2, typename T3>pair<T1, T2> &operator+=(pair<T1, T2> &x, const T3 &y){x.first += y;x.second += y;return x;}template <typename T1, typename T2, typename T3>pair<T1, T2> &operator-=(pair<T1, T2> &x, const T3 &y){x.first -= y;x.second -= y;return x;}ll modpow(ll a, ll b, ll m){ll p = 1, q = a;for (int i = 0; i < 63; ++i){if ((b & (1LL << i)) != 0){p *= q;p %= m;}q *= q;q %= m;}return p;}template <typename T>inline long long EuclideanDist2(const pair<T, T> &p1, const pair<T, T> &p2){long long dx = (long long)p1.first - (long long)p2.first;long long dy = (long long)p1.second - (long long)p2.second;return dx * dx + dy * dy;}template <typename T>inline long long EuclideanDist2(const pair<T, T> &p){return EuclideanDist2(p, make_pair(0, 0));}template <typename T>inline double EuclideanDist(const pair<T, T> &p1, const pair<T, T> &p2){return sqrt((double)EuclideanDist2(p1, p2));}template <typename T>inline double EuclideanDist(const pair<T, T> &p){return sqrt((double)EuclideanDist2(p));}template<typename T>inline long long ManhattanDist(const pair<T, T> &p1, const pair<T, T> &p2){return abs(p1.first - p2.first) + abs(p1.second - p2.second);}template <typename T>T ceil(T x, T y){return (x + y - 1) / y;}template<typename T>T gcd(T a, T b) {if(a < 0) a = -a;if(b < 0) b = -b;if(b == 0) return a;else return gcd(b, a % b);}ull lcm(ull a, ull b) {return a * b / gcd(a, b);}string bitseq(long long x){string ret = "";while(x){ret.push_back('0' + (x & 1));x <<= 1;}reverse(ret.begin(), ret.end());return ret;}#line 2 "code.cpp"#line 2 "library/Compress.hpp"/*** @brief Compress - 座標圧縮*/#line 10 "library/Compress.hpp"using namespace std;struct Compress{int sz;vector<int> to_val;map<int, int> to_index;/*** @brief 配列Vで構築する。*/Compress(vector<int> &V){for(auto &v : V){to_val.emplace_back(v);}sort(to_val.begin(), to_val.end());auto border = unique(to_val.begin(), to_val.end());to_val.erase(border, to_val.end());sz = to_val.size();for(int i = 0; i < sz; ++i){to_index[to_val[i]] = i;}}// 値を対応するインデックスにinline int vi(int value){return to_index[value];}// インデックスを対応する値にinline int iv(int index){return to_val[index];}};#line 2 "library/Graph/GraphTemplate.hpp"/*** @brief Graph Template - グラフテンプレート*/#line 8 "library/Graph/GraphTemplate.hpp"using namespace std;using EdgeNum = int;using Vertex = int;/*** @brief グラフの辺*/template<typename CostType = int>struct Edge{Vertex from, to;CostType cost;Edge(Vertex from, Vertex to, CostType cost) : from(from), to(to), cost(cost){}};/*** @brief グラフを表すクラス。* @note 辺集合によって実現している。* @tparam CostType 辺の重みの型。*/template<typename CostType = int>class Graph{private:int sz;bool dir;vector<int> indegree;public:vector<Edge<CostType>> edges;vector<vector<EdgeNum>> connect;vector<EdgeNum> rev; // 形式上無向グラフでも有向辺を追加するので、辺の追加時に逆辺の辺番号を記録できるようにするCostType INF;/*** @brief Construct a new Graph object* @param VertexNum グラフの頂点数* @param isDirected 有向グラフとして作成するか*/Graph(int VertexNum, bool isDirected = false) : sz(VertexNum), dir(isDirected), connect(VertexNum), indegree(VertexNum), INF(numeric_limits<CostType>::max()){}Graph() = default;/*** @brief グラフに頂点sと頂点t間の辺を追加する。* @note 有向グラフならば頂点sから頂点tへの有向辺を、無向グラフならば頂点sと頂点tを結ぶ無向辺を追加する。* @param s 頂点s* @param t 頂点t* @param w 辺の重み (option, default = 1)*/void add(Vertex s, Vertex t, CostType w = 1){assert(0 <= s && s < sz);assert(0 <= t && t < sz);EdgeNum e = edges.size();edges.push_back(Edge<CostType>(s, t, w));connect[s].push_back(e);++indegree[t];if(!dir){edges.push_back(Edge<CostType>(t, s, w));connect[t].push_back(e + 1);rev.emplace_back(e + 1);rev.emplace_back(e);}}/*** @brief 指定した辺番号の辺を取得する。* @param idx 辺番号* @return Edge<CostType> 辺情報*/Edge<CostType> get_edge(EdgeNum idx){int e = edges.size();assert(0 <= idx && idx < e);return edges[idx];}/*** @brief 指定した頂点番号に接続する辺の一覧を取得する。* @param v 頂点番号* @return vector<Edge<CostType>> 指定した頂点番号に接続する辺の一覧*/vector<Edge<CostType>> get_edges(Vertex v){assert(0 <= v && v < sz);vector<Edge<CostType>> ret;for(auto &idx : connect[v]) ret.push_back(get_edge(idx));return ret;}/*** @brief 指定した頂点番号に接続する辺番号の一覧を取得する。* @param v 頂点番号* @return vector<EdgeNum> 指定した頂点番号に接続する辺番号の一覧*/vector<EdgeNum> get_list(Vertex v){assert(0 <= v && v < sz);return connect[v];}/*** @brief 逆辺を張ったグラフを作成する。* @attention この操作は有向グラフにのみ可能である。* @return Graph<CostType> 逆辺を張ったグラフ*/Graph<CostType> reverse(){assert(dir);Graph<CostType> ret(sz, true);for(auto &e : edges){ret.add(e.to, e.from, e.cost);}return ret;}inline size_t size(){return sz;}inline bool directed(){return dir;}/*** @brief ある頂点の次数(出次数)を取得する。* @note 有向グラフにおいて、第2引数をtrueにすれば入次数を得ることができる。* @param v 頂点番号* @param isIn (有向グラフのときのみ有効)入次数を取得するか (option, default = false)* @return int 頂点vの指定した値*/inline int degree(Vertex v, bool isIn = false){if(dir && isIn) return indegree[v];return (int)connect[v].size();}/*** @brief グラフを頂点rootを根とした無向根付き木とみなしたとき、各頂点の親頂点の番号と、それを結ぶ辺番号を取得する。* @attention グラフが無向木でない場合の動作は未定義である。* @param root 木の根とする頂点番号* @return vector<pair<Vertex, EdgeNum>> 各頂点の親の頂点番号と親への辺番号（頂点rootに対してはどちらも-1とする）*/vector<pair<Vertex, EdgeNum>> get_parent(Vertex root){vector<pair<Vertex, EdgeNum>> ret(sz, pair<Vertex, EdgeNum>(-1, -1));stack<pair<Vertex, Vertex>> st;st.emplace(root, -1);while(!st.empty()){auto [v, parent] = st.top();st.pop();for(auto &idx : connect[v]){if(edges[idx].to == parent) continue;ret[edges[idx].to] = pair<Vertex, EdgeNum>(v, rev[idx]);st.emplace(edges[idx].to, v);}}return ret;}};#line 2 "library/Graph/Dijkstra.hpp"/*** @brief Dijkstra - 単一始点最短距離（ダイクストラ法）*/#line 9 "library/Graph/Dijkstra.hpp"using namespace std;/*** @brief ダイクストラ法で最短距離を求める。* @attention グラフに負の重みの辺がない必要がある。*/template<typename CostType>struct Dijkstra{private:Graph<CostType> &G;vector<Vertex> prev_vertex;public:vector<CostType> dist;Dijkstra(Graph<CostType> &G) : G(G), dist(G.size()), prev_vertex(G.size()){}/*** @brief 頂点sを始点としてダイクストラ法を適用する。* @param s: 始点となる頂点s* @note 求められた最短距離はdistに格納される。*/void build(int s){dist.assign(G.size(), G.INF);prev_vertex.assign(G.size(), -1);using p = pair<CostType, Vertex>;priority_queue<p, vector<p>, greater<p>> que;que.emplace(0, s);dist[s] = 0;while(!que.empty()){auto [d, v] = que.top();que.pop();if(dist[v] < d) continue;for(auto &e : G.get_edges(v)){if(d + e.cost < dist[e.to]){dist[e.to] = d + e.cost;prev_vertex[e.to] = v;que.emplace(d + e.cost, e.to);}}}}/*** @brief 頂点sから頂点tへの最短経路を取得する* @attention 予めbuildで最短距離を求める必要がある。* @param t: 終点となる頂点t* @retval 最短経路*/vector<int> restore(int t){vector<int> ret;int v = t;while(v != -1){ret.push_back(v);v = prev_vertex[v];}reverse(ret.begin(), ret.end());return ret;}};#line 6 "code.cpp"int main(){int N, M;cin >> N >> M;vector<long long> A(M), B(M);vector<int> city{1, N};for(int i = 0; i < M; ++i){cin >> A[i] >> B[i];city.emplace_back(A[i]);city.emplace_back(B[i]);}Compress cp(city);Graph<long long> G(cp.sz);for(int i = 0; i < cp.sz - 1; ++i){G.add(i, i + 1, (cp.iv(i + 1) - cp.iv(i)) * 2LL);}for(int i = 0; i < M; ++i){G.add(cp.vi(A[i]), cp.vi(B[i]), 2 * B[i] - 2 * A[i] - 1);}Dijkstra dk(G);dk.build(0);cout << dk.dist[cp.sz - 1] << endl;}