aoj 1176 Planning Rolling Blackouts

問題

問題概要

長方形が与えられ, そのますに値が入っている. 長方形を分割してくが, 分割方法は区切られた長方形を一つ選び, それを縦か横どちらに切って分ける.
分割できるのは, 分割後に任意のグループを一つ選び, 抑制需要(残ったグループのますの値の合計値)が供給量を超えてはならない. さらに分割数を最大にし, さらに予備力(供給力と最大抑制需要の差)を最大にしなければならない.

解法

まず長方形の角を指定したら, その中のマスの値の合計値がO(1)で求まるように, 二次元累積和用いて計算できるようにしておく.
あとは, dp[y1][x1][y2][x2] := 左上(y1, x1), 右下(y2, x2)の長方形を考えた時の, グループの分け方の最大数と最大の予備力
という状態を考えてdpしていく.
ある長方形を考えた時に, 分割する方法は縦にどこかで切るか, 横にどこかで切るか(またはこれ以上きれない)しかないのでこれらをすべて試せば良い. これをdfsの中で行っている. 値の更新方法は長方形を切り, 作られた2つの長方形それぞれのグループの分け方と予備力の最大値を用いて, 更新することができる. グループの分け方は2つの長方形の値を単に足せばよくて, 予備力は供給力と最大抑制需要の差のことなので, 2つの長方形の値の最小値をつかえばよい.

ミス

長方形を分割していくのは再起関数で書くと楽ですね.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = max(a, b);
#define chmin(a, b) a = min(a, b);
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int h, w, s;
int U[35][35];
int allsum = 0;
int sum[35][35];
// dp[y1][x1][y2][x2] := 左上(y1, x1), 右下(y2, x2)の長方形を考えた時の, 
// グループの分け方の最大数, 最大の予備力
pair<int, int> dp[35][35][35][35];

void sum2D(int h, int w) {
    rep(y, h + 1)rep(x, w + 1) sum[y][x] = 0;
    rep(y, h)rep(x, w) sum[y + 1][x + 1] = U[y][x]; // まずは埋め込む
    rep(y, h + 1)rep(x, w) sum[y][x + 1] += sum[y][x]; // 横
    rep(y, h)rep(x, w + 1) sum[y + 1][x] += sum[y][x]; // 縦
}
int calcSum(int y1, int x1, int y2, int x2) {
    return sum[y2 + 1][x2 + 1] - sum[y2 + 1][x1] - sum[y1][x2 + 1] + sum[y1][x1];
}

pair<int, int> dfs(int y1, int x1, int y2, int x2) {
    if(dp[y1][x1][y2][x2] != make_pair(0, INF)) return dp[y1][x1][y2][x2];
    
    auto ret = make_pair(1, s - (allsum - calcSum(y1, x1, y2, x2))); // これ以上分割できない場合の値

    for (int i = x1; i < x2; ++i){
        if(s - (allsum - calcSum(y1, x1, y2, i)) < 0) continue;
        if(s - (allsum - calcSum(y1, i + 1, y2, x2)) < 0) continue;
        auto ret1 = dfs(y1, x1, y2, i);
        auto ret2 = dfs(y1, i + 1, y2, x2);
        chmax(ret, make_pair(ret1.fi + ret2.fi, min(ret1.se, ret2.se)));
    }

    for (int i = y1; i < y2; ++i){
        if(s - (allsum - calcSum(y1, x1, i, x2)) < 0) continue;
        if(s - (allsum - calcSum(i + 1, x1, y2, x2)) < 0) continue;
        auto ret1 = dfs(y1, x1, i, x2);
        auto ret2 = dfs(i + 1, x1, y2, x2);
        chmax(ret, make_pair(ret1.fi + ret2.fi, min(ret1.se, ret2.se)));
    }
    return dp[y1][x1][y2][x2] = ret;
}

int main(void) {
    while(1) {
        scanf("%d %d %d", &h, &w, &s);

        if(h == 0 && w == 0 && s == 0) break;
        rep(i, h)rep(j, w) scanf("%d", &U[i][j]);
        allsum = 0;
        rep(i, h)rep(j, w) allsum += U[i][j];
        sum2D(h, w);
        rep(i, 35)rep(j, 35)rep(k, 35)rep(l, 35) dp[i][j][k][l] = make_pair(0, INF);
        auto ans = dfs(0, 0, h - 1, w - 1);
        printf("%d %d\n", ans.fi, ans.se);
    }
    return 0;
}

Codeforces #223 Div1. C. Sereja and Brackets

問題

問題概要

‘('と’)‘が含まれた文字列が与えられる. その文字列のl番目からからr番目のまでの文字を考えたときに, その中にカッコの対応が最大でいくつできるかを書くクエリごとに答える.

解法

segtreeを使えばよい. 状態として区間[l, r)の中で,
すでにカッコの対応が作られている文字の数
まだ使われていない ‘(’ の数
また使われていない ‘)’ の数
を持つようにすればよい.
演算は左の区間の'(‘ の数と, 右の区間の’)‘の数の最小値の2倍をその区間で対応付けられたカッコの数に足せばよい. 例えば左の区間が )(())( で, 右の区間が )()() の場合, 左はすでに対応付けられているのが4, ’(‘が1, ’)‘が1となっている. 右はすでに対応付けられているのが4, ’)‘が1, ’(‘が0となっている.
新たに対応付けられるのは, 左の’(‘の数, 右の’)‘の数の最小値なので,1組となる. よって, 演算の結果は,　 すでに対応付けられているのが, 8, ’(‘が 0, ’)‘が 1となっている.
また, 非可換なので演算の順番に注意.

ミス

左右の区間を見てすでにカッコの対応が付いているものは, 使われていない部分だけで新たにカッコの対応が作れるかを考えればよいということに気づくのに時間がかかる.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

template <class T> //T(モノイド) : dat[]の中身の型
class segtree{
public:
    int n;
    T neutral;
    vector<T> dat;
    T func(T l, T r) { //二項演算子
        int lok, lopen, lclose, rok, ropen, rclose;
        tie(lok, lopen, lclose) = l;
        tie(rok, ropen, rclose) = r;
        int add = min(lopen, rclose);
        return make_tuple(lok + rok + 2 * add, lopen + ropen - add, lclose + rclose - add);
    }
    segtree(int n_, T val): n(n_), neutral(val) { //n_:要素数 val:単位元
        n = 1;
        while(n < n_) n *= 2;
        dat.resize(n * 2, neutral); //初期値
    }
    void update(int k, T val){ // k番目の値(0-indexed)を val に変更
        k += n - 1;
        dat[k] = val;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    T query(int a, int b, int k, int l, int r) { //[a, b)の区間
        if(r <= a || b <= l) return neutral;
        if(a <= l && r <= b) return dat[k];
        else {
            T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return func(vl, vr);
        }
    }
    T query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};


int m, l[100010], r[100010];
int main(void) {
    string s; cin >> s;
    segtree<tuple<int, int, int>> seg(s.size(), make_tuple(0, 0, 0));
    rep(i, s.size()) {
        if(s[i] == '(') seg.update(i, make_tuple(0, 1, 0));
        else seg.update(i, make_tuple(0, 0, 1));
    }

    scanf("%d", &m);
    rep(i, m) scanf("%d %d", &l[i], &r[i]);
    rep(i, m){
        auto ret = seg.query(l[i] - 1, r[i]);
        int a, b, c; tie(a, b, c) = ret;
        printf("%d\n", a);
    }
    return 0;
}

C言語 ポインタ同士の引き算

アドレスの差分にはならない.

int main(void){
    int a[2];
    int k = &a[1] - &a[0];
    return 0;
}

上のコードを実行したら, kを表示すると結果は1となる. 4ではない. ポインタ同士の引き算は内部でアドレスの値を引いた後にそのポインタが指している変数の型のバイト数(sizeof(変数の型))で割った結果を求めるようにコンパイラは働く.
実際に上のコードをコンパイルしたアセンブラを見ると,

0000000100000f9e <_main>:
   100000f9e:   55                      push   rbp
   100000f9f:   48 89 e5                mov    rbp,rsp
   100000fa2:   c7 45 fc 01 00 00 00    mov    DWORD PTR [rbp-0x4],0x1  //変数kに1が代入されている
   100000fa9:   b8 00 00 00 00          mov    eax,0x0
   100000fae:   5d                      pop    rbp
   100000faf:   c3                      ret 

のようになっている. これは最適化を切ってコンパイルした結果である.
連続領域の場合最適化を切っていても, コンパイル時に相対距離が計算できるので, コンパイル時に計算してしまうようだ(下記の結果から推測).

次に, 連続領域に存在しないポインタの引き算を実行してみる.

int main(void){
    int a[2], b[2];
    int k = &b[0] - &a[0];
    return 0;
}

上のコードを最適化を切って, 　コンパイルしたアセンブラは以下のようになる.

0000000100000f90 <_main>:
   100000f90:   55                      push   rbp
   100000f91:   48 89 e5                mov    rbp,rsp
   100000f94:   48 8d 55 e0             lea    rdx,[rbp-0x20] // rdx に &b[0]を代入
   100000f98:   48 8d 45 f0             lea    rax,[rbp-0x10] // rax に &a[0]を代入
   100000f9c:   48 29 c2                sub    rdx,rax // rdxからraxを引く
   100000f9f:   48 89 d0                mov    rax,rdx // rdxの値をraxに代入
   100000fa2:   48 c1 f8 02             sar    rax,0x2 //raxの値を右へシフト2する (rax /= 4)
   100000fa6:   89 45 fc                mov    DWORD PTR [rbp-0x4],eax //変数kに代入する
   100000fa9:   b8 00 00 00 00          mov    eax,0x0
   100000fae:   5d                      pop    rbp
   100000faf:   c3                      ret

今回はコンパイル時には計算できないようで, sizeof(int)で割る処理が行なわれている(sar rax,0x2).

double 型でも同様なことをやっておく.

int main(void){
    double a, b;
    int k = &a - &b; //1
    int l = &b - &a; //-1
    return 0;
}

0000000100000f7b <_main>:
   100000f7b:   55                     push   rbp
   100000f7c:   48 89 e5               mov    rbp,rsp
   100000f7f:   48 8d 55 f0            lea    rdx,[rbp-0x10] // rdx = &a;
   100000f83:   48 8d 45 e8            lea    rax,[rbp-0x18] // rax = &b;
   100000f87:   48 29 c2               sub    rdx,rax // rdx -= rax;
   100000f8a:   48 89 d0               mov    rax,rdx // rax = rdx;
   100000f8d:   48 c1 f8 03             sar    rax,0x3 // rax >>= 3; (rax /= sizeof(double))
   100000f91:   89 45 fc               mov    DWORD PTR [rbp-0x4],eax // k = eax;
   100000f94:   48 8d 55 e8            lea    rdx,[rbp-0x18] // rdx = &b;
   100000f98:   48 8d 45 f0            lea    rax,[rbp-0x10] // rax = &a;
   100000f9c:   48 29 c2               sub    rdx,rax // rdx -= rax;
   100000f9f:   48 89 d0               mov    rax,rdx  // rax = rdx;
   100000fa2:   48 c1 f8 03             sar    rax,0x3 // rax >>= 3 (rax /= sizeof(double))
   100000fa6:   89 45 f8               mov    DWORD PTR [rbp-0x8],eax // l = eax;
   100000fa9:   b8 00 00 00 00          mov    eax,0x0 // return 0;を設定
   100000fae:   5d                      pop    rbp
   100000faf:   c3                       ret  

上記はコードとそのアセンブラの結果である.
sar rax,0x3
という命令があり, 右へ3シフトする. つまり sizeof(double) で割っているということ.

実際のポインタの値同士の引き算をするには?

int main(void){
    int a[2];
    int k = (int)&a[1] - (int)&a[0];
    return 0;
}

上のコードのkには4が代入される. int型にキャストしてから演算すればいい.

Codeforces #197 Div2 D Xenia and Bit Operations

問題

問題概要

奇数回目に数列を左から隣同士を見て, ORを計算し, 偶数回目に数列を左から見て, XORを計算する. それぞれのステップで数列の要素数は半分になる. 数列の要素数が1になるまでこれを繰り返す.
はじめの数列がm回変化するので, m個の数列に対して要素数が1になるときの値を求める.

解法

奇数回目の計算はORで, 偶数回目はXORで計算しなければならないので, updata()関数で場合分けをして計算しなければならない. また, ORとXORの単位元は0なので, 初期値を0にして更新する. さらに, ORとXORは結合法則を満たすのでsegment treeのデータ構造を用いても問題ない. 以上のこと以外は, 通常のsegtreeと同じようにやればよい.

ミス

nは数列の数でないので注意.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define OUT(x) cout << #x << " = " << x << endl; 
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

template <class T> //T : dat[]の中身の型
class segtree{
public:
    int n;
    vector<T> dat;
    segtree(int n_): n(n_){ //n_要素数
        n = 1;
        while(n < n_) n *= 2;
        dat.resize(n * 2, 0); //(1) 単位元
    }
    void update(int k, T val){ // k番目の値(0-indexed)を val に変更
        k += n - 1; //葉の節点
        dat[k] = val;
        int cnt = 0;
        while(k > 0){
            k = (k - 1) / 2;
            if(cnt % 2)dat[k] = dat[k * 2 + 1] ^ dat[k * 2 + 2];
            else dat[k] = dat[k * 2 + 1] | dat[k * 2 + 2];
            cnt++;
        }
    }
};

int n, m;

int main(void){
    cin >> n >> m;
    segtree<int> seg(pow(2, n)); //大きさに注意
    rep(i, pow(2, n)){
        int a; cin >> a;
        seg.update(i, a);
    }
    
    rep(i, m){
        int p, b; cin >> p >> b;
        p--;
        seg.update(p, b);
        printf("%d\n", seg.dat[0]);
    }

    return 0;
}

ABC 009 D - 漸化式

問題

問題概要

与えられた漸化式によって導かれるM番目の値を求めよ.

解法

andとxorの演算は, (G, 和, 積) := ({1,0}, xor, and)とすると, 環をなしている. また, 行列の演算は半環であれば, 成り立つ. これらのことから, 通常の行列ライブラリの和をxorへ, 積をandへ置換しても, 行列演算が行える.
注意する点は, andの単位元は1ではなく, 全ての桁に1を用意しなければならないので, 0xffffffffなどとしている.

ミス

行列計算の単位元を1のままやっていた. andとxorはそれぞれの桁に対して行われる演算なので, すべての桁に1を入れておく必要がある.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ll INFF = 1e18;

// N*N行列Aを作りたい場合 mat A(N, vec(N));
typedef vector<long long> vec;
typedef vector<vec> mat;
// +->and *->xor
mat mul(mat &A,mat &B){ // A * B の計算
    mat C(A.size(), vec(B[0].size()));
    for(int i = 0; i < A.size(); i++){
        for(int k = 0; k < B.size(); k++){
            for(int j = 0; j < B[0].size(); j++){
                C[i][j] = C[i][j] ^ (A[i][k] & B[k][j]); //演算子置き換え
            }
        }
    }
    return C;
}
mat pow(mat A, long long n){ // A^n の計算
    mat B(A.size(), vec(A.size()));
    for(int i = 0; i < A.size(); i++){
        B[i][i] = 0xffffffffffffffff; //単位元 全ての桁に1が必要
    }
    while(n > 0){
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

int main(void){
    int K, M;
    long long A[110], C[110];
    cin >> K >> M;
    rep(i, K) cin >> A[i];
    rep(i, K) cin >> C[i];
    if(M <= K) {
        cout << A[M - 1] << endl;
        return 0;
    }
    mat B(K, vec(K, 0));
    rep(i, K) B[0][i] = C[i];
    rep(i, K - 1) B[i + 1][i] = 0xffffffffffffffff; //単位元 全ての桁に1が必要
    auto Bn = pow(B, M - K);

    mat A0(K, vec(1));
    rep(i, K) A0[i][0] = A[K - 1 - i];
    auto ret = mul(Bn, A0);
    printf("%lld\n", ret[0][0]);
    return 0;
}

ABC 029 D - 1

問題

問題概要

1以上N以下の全ての数字のなかに数字1が全部でいくつ含まれているか?

解法

脳死しているので桁dpをする.
dp[i][j][k] := i桁目まで見て, j==1ならNより小さい, 1を使った数がk回となる数字の総数
という状態を決めてやればいい. 漸化式の遷移はすでにNより小さいのかどうかで場合分けした後, 今見ている桁が0, 1またはそれ以外で場合分けして丁寧にj, kの値を決めていけば大丈夫.

ミス

dpの状態を決めるのに悩んだ.
求めたいものが数字1の総数なので, dp[i][j]:= (上記)ijの時の1を使った数 という状態としてしまった.
状態数に求めたいものをいれることだってあるので注意. 桁dpは決めた状態を満たす数字の総数をメモっていくと考えておこう.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

string N;
ll dp[12][2][12];
// dp[i][j][k] := i桁目まで見て, j==1ならNより小さい, 1を使った数がk回となる　数字の総数

int main(void){
    cin >> N;
    rep(i, 12)rep(j, 2)rep(k, 12) dp[i][j][k] = 0;
    dp[0][0][0] = 1;

    rep(i, N.size()){
        rep(j, 2)rep(k, 12){
            if(dp[i][j][k] == 0) continue;
            if(j == 1){ // N より小さい
                dp[i + 1][1][k + 1] += dp[i][j][k]; // 1を選ぶ
                dp[i + 1][1][k] += dp[i][j][k] * 9; // 0,2, .. 9 を選ぶ
            }else{
                if(N[i] == '1'){
                    dp[i + 1][0][k + 1] += dp[i][j][k]; //1を選ぶ
                    dp[i + 1][1][k] += dp[i][j][k]; //0を選ぶ
                }else if(N[i] == '0'){
                    dp[i + 1][0][k] += dp[i][j][k]; //0を選ぶ
                }else{//2 <= N[i] <= 9
                    dp[i + 1][0][k] = dp[i][j][k]; // N[i]を選ぶ
                    dp[i + 1][1][k] = dp[i][j][k] * ((N[i] - '0') - 1); //2 ~ N[i]-1
                    dp[i + 1][1][k + 1] += dp[i][j][k]; //1を選ぶ
                }
            }
        }
    }
    ll ans = 0;
    rep(j, 2)rep(k, 12){
        if(dp[(int)N.size()][j][k]){
            ans += k * dp[(int)N.size()][j][k];
        }
    }
    cout << ans << endl;
    return 0;
}

CODE THANKS FESTIVAL 2015 G - カメレオン

問題

問題概要

頂点1からNまでの最短コストを求めよ. ただし辺のコストtに加えて, 辺を通る時の色が決められているので, 色を変えるのにもコストがかかる. xからyに色を変える場合のコストは, |x-y|である.

解法

拡張ダイクストラをすればいい.
dist[i][j]として 頂点0からiまで, iへ色jで来た時の最小コストとして ダイクストラで計算していけばいい. ただし, 今回の問題で普通に2次元配列を取るとMLEしてしまう. しかし, 頂点iで可能性のある色は, iと隣接する辺で指定される色のみなので, dist[i][j]のjは実際は全種類の色の総数分の空間を用意しなくて良いことになる.
ではどうするかだが, dist[i]を必要な分だけ拡張すればよいかなと考えたが, めんどくさいので, map<int, ll> dist[] とすることで, dist[i][j]のjが必要な分だけ用意できることになる.

ミス

2次元配列が欲しくて, そのままではMLEしてしまうが, 2つめの要素がまばらな時, mapを使えば楽に空間を減らせる.

mapの使い方に注意
dist[v]にkey=ncが登録されていないか, 登録されていたとしても, ncostより大きかを調べる場合に,

if(dist[v][nc] > ncost || dist[v].count(nc) == 0)

ではだめ.

if(dist[v].count(nc) == 0 || dist[v][nc] > ncost)

としなければならない.
std::mapは[]演算子で存在しない要素にアクセスすると自動的に追加されるしまうので, 左側に(先に評価される方)dist[v][nc]とすると, key=ncの要素がないのに作られてしまい, 右側の評価が意味のないものになってしまった.

std::map - C++入門

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;

int N, M;
int a[80010], b[80010], c[80010], t[80010];

using tup = tuple<ll, int, int>;
vector<tuple<int, int, int>> G[40010]; // G[i] := i->j color time
//dist[i][j] := 頂点iへcolor jでつくときのコストの最小値
map<int, ll> dist[40010];
void dijkstra(int start){
    priority_queue<tup, vector<tup>, greater<tup>> que; // コスト 位置 color
    dist[start][1] = 0;
    que.push(make_tuple(0, start, 1));
    while(!que.empty()){
        ll cost; int u, color;
        tie(cost, u, color) = que.top(); que.pop();
        if(dist[u][color] < cost) continue; // これでTLE回避
        if(u == N - 1) break;
        for(auto tm : G[u]){
            int v, nc, nt;
            tie(v, nc, nt) = tm;
            ll ncost = cost + abs(nc - color) + nt;
            // if(dist[v][nc] > ncost || dist[v].count(nc) == 0){ // dist[v][nc]の要素ができてしまう
            if(dist[v].count(nc) == 0 || dist[v][nc] > ncost){
                dist[v][nc] = ncost;
                que.push(make_tuple(ncost, v, nc));
            }
        }
    }
}

int main(void){
    scanf("%d %d", &N, &M);
    rep(i, M) scanf("%d %d %d %d", &a[i], &b[i], &c[i], &t[i]);
    rep(i, M){
        a[i]--; b[i]--;
        G[a[i]].pb(make_tuple(b[i], c[i], t[i]));
        G[b[i]].pb(make_tuple(a[i], c[i], t[i]));
    }
    dijkstra(0);
    ll ans = INFF;
    for(auto u : dist[N - 1]){
        chmin(ans, u.se);
    }
    printf("%lld\n", ans);
    return 0;
}