#line 2 "library/Template.hpp" /** * @brief Procon Template - テンプレート */ #include #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 bool minin(T &src, const T &cmp){if(src > cmp){src = cmp; return true;}return false;} template bool maxin(T &src, const T &cmp){if(src < cmp){src = cmp; return true;}return false;} template inline bool between(T min, T x, T max){return min <= x && x <= max;} template 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::max() / 2; const long long INF_LL = numeric_limits::max() / 2LL; template using vec = vector; using pi = pair; using pll = pair; using pd = pair; template using pq = priority_queue; template using rpq = priority_queue, greater>; 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 ostream &operator<<(ostream &os, const pair &p){ os << "{" << p.first << " " << p.second << "}"; return os; } template istream &operator>>(istream &is, pair &p){ is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, vector &v){ for (int i = 0; i < v.size(); ++i){ os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template ostream &operator<<(ostream &os, vector> &v){ for (int i = 0; i < v.size(); ++i){ os << v[i] << "\n"; } return os; } template istream &operator>>(istream &is, vector &v){ for (int i = 0; i < v.size(); ++i) is >> v[i]; return is; } template istream &operator>>(istream &is, valarray &v){ for (int i = 0; i < v.size(); ++i) is >> v[i]; return is; } template pair &operator+=(pair &x, const T3 &y){ x.first += y; x.second += y; return x; } template pair &operator-=(pair &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 inline long long EuclideanDist2(const pair &p1, const pair &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 inline long long EuclideanDist2(const pair &p){ return EuclideanDist2(p, make_pair(0, 0)); } template inline double EuclideanDist(const pair &p1, const pair &p2){ return sqrt((double)EuclideanDist2(p1, p2)); } template inline double EuclideanDist(const pair &p){ return sqrt((double)EuclideanDist2(p)); } template inline long long ManhattanDist(const pair &p1, const pair &p2){ return abs(p1.first - p2.first) + abs(p1.second - p2.second); } template T ceil(T x, T y){ return (x + y - 1) / y; } template 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 to_val; map to_index; /** * @brief 配列Vで構築する。 */ Compress(vector &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 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 class Graph{ private: int sz; bool dir; vector indegree; public: vector> edges; vector> connect; vector 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::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(s, t, w)); connect[s].push_back(e); ++indegree[t]; if(!dir){ edges.push_back(Edge(t, s, w)); connect[t].push_back(e + 1); rev.emplace_back(e + 1); rev.emplace_back(e); } } /** * @brief 指定した辺番号の辺を取得する。 * @param idx 辺番号 * @return Edge 辺情報 */ Edge get_edge(EdgeNum idx){ int e = edges.size(); assert(0 <= idx && idx < e); return edges[idx]; } /** * @brief 指定した頂点番号に接続する辺の一覧を取得する。 * @param v 頂点番号 * @return vector> 指定した頂点番号に接続する辺の一覧 */ vector> get_edges(Vertex v){ assert(0 <= v && v < sz); vector> ret; for(auto &idx : connect[v]) ret.push_back(get_edge(idx)); return ret; } /** * @brief 指定した頂点番号に接続する辺番号の一覧を取得する。 * @param v 頂点番号 * @return vector 指定した頂点番号に接続する辺番号の一覧 */ vector get_list(Vertex v){ assert(0 <= v && v < sz); return connect[v]; } /** * @brief 逆辺を張ったグラフを作成する。 * @attention この操作は有向グラフにのみ可能である。 * @return Graph 逆辺を張ったグラフ */ Graph reverse(){ assert(dir); Graph 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> 各頂点の親の頂点番号と親への辺番号(頂点rootに対してはどちらも-1とする) */ vector> get_parent(Vertex root){ vector> ret(sz, pair(-1, -1)); stack> 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(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 struct Dijkstra{ private: Graph &G; vector prev_vertex; public: vector dist; Dijkstra(Graph &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; priority_queue, greater

> 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 restore(int t){ vector 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 A(M), B(M); vector 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 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; }