結果

問題 No.1283 Extra Fee
ユーザー nazcazcannazcazcan
提出日時 2020-11-06 22:25:48
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,129 ms / 2,000 ms
コード長 8,305 bytes
コンパイル時間 4,453 ms
コンパイル使用メモリ 248,112 KB
実行使用メモリ 98,892 KB
最終ジャッジ日時 2023-08-10 06:02:04
合計ジャッジ時間 19,398 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,384 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,384 KB
testcase_11 AC 28 ms
7,744 KB
testcase_12 AC 34 ms
8,660 KB
testcase_13 AC 21 ms
7,108 KB
testcase_14 AC 140 ms
19,996 KB
testcase_15 AC 251 ms
30,112 KB
testcase_16 AC 37 ms
8,960 KB
testcase_17 AC 664 ms
77,480 KB
testcase_18 AC 1,044 ms
90,644 KB
testcase_19 AC 1,099 ms
95,616 KB
testcase_20 AC 1,012 ms
89,852 KB
testcase_21 AC 1,008 ms
91,220 KB
testcase_22 AC 914 ms
81,968 KB
testcase_23 AC 1,100 ms
98,832 KB
testcase_24 AC 1,105 ms
98,724 KB
testcase_25 AC 1,129 ms
98,872 KB
testcase_26 AC 1,111 ms
98,864 KB
testcase_27 AC 1,091 ms
98,844 KB
testcase_28 AC 1,106 ms
98,892 KB
testcase_29 AC 666 ms
83,060 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

constexpr bool isDebugMode = false;
int testcase = 1;
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
    #include <atcoder/all>
    using namespace atcoder;
#endif
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007; //998244353;
const long long dy[] = {-1, 0, 0, 1};
const long long dx[] = {0, -1, 1, 0};
const string abc = "abcdefghijklmnopqrstuvwxyz";
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for (const auto &e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void pt(){cout << endl; return;}
template<class Head> void pt(Head&& head){cout << head; pt(); return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
void dpt(){if(!isDebugMode) return; cout << endl; return;}
template<class Head> void dpt(Head&& head){if(!isDebugMode) return; cout << head; pt(); return;}
template<class Head, class... Tail> void dpt(Head&& head, Tail&&... tail){if(!isDebugMode) return; cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void enu(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void enu2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T> void debug(T v){if(!isDebugMode) return; rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){if(!isDebugMode) return; rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2> long long recgcd(T1 a, T2 b){return a % b ? recgcd(b, a % b) : b;}
bool valid(long long H, long long W, long long h, long long w) { return 0 <= h && h < H && 0 <= w && w < W; }

void solve();

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // cin >> testcase;
    while(testcase--) solve();
    return 0;
}

struct Graph{
public:
ll V, logV;
vector<vector<edge>> Glist;
vector<vector<ll>> Gmatrix;
vector<ll> LCA_dist;
vector<vector<ll>> LCA_doubling;

Graph(ll NodeNum){
    V = NodeNum;
    Glist.resize(V);
}
    void add(ll from,ll to,ll cost = 1){
        Glist[from].push_back({to,cost});
    }
    void bidadd(ll from,ll to,ll cost = 1){
        Glist[from].push_back({to, cost});
        Glist[to].push_back({from, cost});
    }

    void express(){
        for(ll i = 0; i < Glist.size(); i++){
            cout << i << " => {";
            eachdo(Glist[i], e){
                cout << " " << e.to;
            } 
            cout << " }" << endl;
        }
        return;
    }

    void UpdateGmatrix() {
        Gmatrix.resize(V);
        rep(i,V){
            Gmatrix[i].resize(V,INF);
            eachdo(Glist[i],e){
                Gmatrix[i][e.to] = e.cost;
            }
        }
    }

    vector<vector<ll>> WarshallFloyd(){
        UpdateGmatrix();
        vector<vector<ll>> dist = Gmatrix;
        rep(i,V) dist[i][i] = 0;
        rep(k,V)rep(i,V)rep(j,V) chmin(dist[i][j],dist[i][k]+dist[k][j]);
        return dist;
    }

    vector<bool> hasNegativeLoop(){
        vector<bool> ret(V,false);
        vector<ll> dist(V,0);
        rep(loop,2*V-1){
            rep(i,V)eachdo(Glist[i],e){
                if(dist[i] + e.cost < dist[e.to]){
                    dist[e.to] = dist[i] + e.cost;
                    if(V-1 <= loop) ret[e.to] = true;        
                }
            }
        }
        return ret;
    }

    vector<ll> BellmanFord(ll start){
        vector<ll> dist(V,INF);
        dist[start] = 0;
        rep(loop,V-1){
            rep(i,V)eachdo(Glist[i],e){
                if(dist[i] + e.cost < dist[e.to]){
                    dist[e.to] = dist[i] + e.cost;        
                }
            }
        }
        return dist;
    }

    vector<ll> Dijkstra(ll start){
        vector<ll> dist(V,INF);
        priority_queue<P,vector<P>,greater<P>> que;
        dist[start] = 0;
        que.push(P(0,start)); 
        while(!que.empty()){
            P p = que.top();que.pop();
            ll v = p.second;
            if(dist[v]<p.first) continue;
            rep(i,Glist[v].size()){
                edge e = Glist[v][i];
                if(dist[v] + e.cost < dist[e.to]){
                    dist[e.to] = dist[v]+e.cost;
                    que.push(P(dist[e.to],e.to));
                }
            }
        }
        return dist;
    }

    // Graph needs to be undirected tree.
    void dfs_in_build_LCA(ll node, ll parent = -1){
        if (parent != -1) LCA_dist[node] = LCA_dist[parent] + 1;
        LCA_doubling[0][node] = parent;
        for(auto e : Glist[node]){
            if (e.to == parent) continue;
            dfs_in_build_LCA(e.to, node);
        }
    }

    void build_LCA(ll root){
        LCA_dist.assign(V, INF);
        logV = 1;
        while(1 << logV < V) logV++;
        LCA_dist.assign(V, INF);
        LCA_doubling.assign(logV, vector<ll>(V, -1));
        LCA_dist[root] = 0;
        dfs_in_build_LCA(root);
        for(ll i = 1; i < logV; i++){
            for(ll j = 0; j < V; j++){
                if (LCA_doubling[i - 1][j] == -1){
                    LCA_doubling[i][j] = -1;
                    continue;
                }
                LCA_doubling[i][j] = LCA_doubling[i - 1][LCA_doubling[i - 1][j]];
            }
        }
    }

    ll LCA_query(ll u, ll v){
        if (LCA_dist[v] < LCA_dist[u]) swap(u, v);
        ll upstream = LCA_dist[v] - LCA_dist[u];
        for(ll i = 0; i < logV; i++){
            if (upstream >> i & 1) v = LCA_doubling[i][v]; 
        }
        ll ng = -1, ok = V;
        while(ok - ng > 1){
            ll half = (ng + ok) / 2;
            ll ua = u, va = v;
            for(ll i = 0; i < logV; i++){
                if (half >> i & 1){
                    if (ua == -1 || va == -1){
                        ua = -1;
                        va = -1;
                        break;
                    }
                    ua = LCA_doubling[i][ua];
                    va = LCA_doubling[i][va];
                }
            }

            if (ua == va) ok = half;
            else ng = half;
        }
        ll ret = u;
        for(ll i = 0; i < logV; i++){
            if (ok >> i & 1) ret = LCA_doubling[i][ret]; 
        }
        return ret;
    }

    ll path_dist(ll u, ll v){
        return LCA_dist[u] + LCA_dist[v] - 2 * LCA_dist[LCA_query(u, v)];
    }

    bool is_on_path(ll u, ll v, ll x){
        return path_dist(u, x) + path_dist(x, v) == path_dist(u, v); 
    }
};
ll N;
ll has(ll h, ll w, ll u){
    return u * (N * N) + h * N + w;
}

void solve(){
    ll M; cin >> N >> M;
    vector<ll> h(M), w(M), c(M);
    rep(i, M) cin >> h[i] >> w[i] >> c[i];
    rep(i, M){
        h[i]--;
        w[i]--;
    }
    Graph g(N * N * 2 + 100);
    set<ll> bad;
    rep(i, M) bad.insert((h[i] * N + w[i]));
    rep(i, N)rep(j, N){
        if(bad.count(i * N + j)) continue;
        rep(k, 4)rep(b, 2){
            if(valid(N, N ,i + dx[k], j + dy[k])) g.add(has(i + dx[k], j + dy[k], b), has(i, j, b), 1);
        }
    }
    rep(i, M){
        rep(k, 4){
            if(valid(N, N ,h[i] + dx[k], w[i] + dy[k])) g.add(has(h[i] + dx[k], w[i] + dy[k], 1), has(h[i], w[i], 1), c[i] + 1);
            if(valid(N, N ,h[i] + dx[k], w[i] + dy[k])) g.add(has(h[i] + dx[k], w[i] + dy[k], 0), has(h[i], w[i], 0), c[i] + 1);
            if(valid(N, N ,h[i] + dx[k], w[i] + dy[k])) g.add(has(h[i] + dx[k], w[i] + dy[k], 0), has(h[i], w[i], 1), 1);
        }
    }
    pt(min(g.Dijkstra(0)[has(N - 1, N - 1, 0)], g.Dijkstra(0)[has(N - 1, N - 1, 1)]));
}
0