結果
| 問題 |
No.1995 CHIKA Road
|
| コンテスト | |
| ユーザー |
 log_K
|
| 提出日時 | 2023-07-12 09:46:14 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 537 ms / 2,000 ms |
| コード長 | 14,292 bytes |
| コンパイル時間 | 2,864 ms |
| コンパイル使用メモリ | 225,932 KB |
| 最終ジャッジ日時 | 2025-02-15 10:01:12 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
ソースコード
#line 1 "yuki-1995.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1995"
#line 2 "/mnt/c/Users/koji0/Desktop/Procon/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 REVERSE(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;
#ifndef ONLINE_JUDGE
void dprint(){
cerr << endl;
}
template<class Head, class... Tail>
void dprint(Head&& head, Tail&&... tail){
cerr << head << " ";
dprint(forward<Tail>(tail)...);
}
#else
template<class Head, class... Tail>
void dprint(Head&& head, Tail&&... tail){}
#endif
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;
using ld = long double;
const long double PI = acosl(-1);
const long double PI2 = PI * 2;
const long 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 4 "yuki-1995.test.cpp"
#line 2 "/mnt/c/Users/koji0/Desktop/Procon/library/Compress.hpp"
/**
* @brief Compress - 座標圧縮
*/
#line 10 "/mnt/c/Users/koji0/Desktop/Procon/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 "/mnt/c/Users/koji0/Desktop/Procon/library/Graph/GraphTemplate.hpp"
/**
* @brief Graph Template - グラフテンプレート
*/
#line 8 "/mnt/c/Users/koji0/Desktop/Procon/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 "/mnt/c/Users/koji0/Desktop/Procon/library/Graph/Dijkstra.hpp"
/**
* @brief Dijkstra - 単一始点最短距離（ダイクストラ法）
*/
#line 9 "/mnt/c/Users/koji0/Desktop/Procon/library/Graph/Dijkstra.hpp"
using namespace std;
/**
* @brief ダイクストラ法で最短距離を求める。
* @attention グラフに負の重みの辺がない必要がある。
*/
template<typename CostType>
struct Dijkstra{
private:
Graph<CostType> &G;
vector<Vertex> prev_vertex;
vector<EdgeNum> prev_edge;
public:
vector<CostType> dist;
Dijkstra(Graph<CostType> &G) : G(G), dist(G.size()), prev_vertex(G.size()), prev_edge(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);
prev_edge.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 &eidx : G.get_list(v)){
auto e = G.get_edge(eidx);
if(d + e.cost < dist[e.to]){
dist[e.to] = d + e.cost;
prev_vertex[e.to] = v;
prev_edge[e.to] = eidx;
que.emplace(d + e.cost, e.to);
}
}
}
}
/**
* @brief 頂点sから頂点tへの最短経路を取得する
* @attention 予めbuildで最短距離を求める必要がある。
* @param t: 終点となる頂点t
* @param isEdge: 頂点番号の代わりに辺番号を取得する(opt default = false)
* @retval 最短経路の頂点番号 or 辺番号
*/
vector<int> restore(int t, bool isEdge = false){
vector<int> ret;
int v = t;
while(v != -1){
if(!isEdge) ret.push_back(v);
else if(prev_edge[v] != -1) ret.push_back(prev_edge[v]);
v = prev_vertex[v];
}
reverse(ret.begin(), ret.end());
return ret;
}
};
#line 8 "yuki-1995.test.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;
}