結果
| 問題 |
No.1283 Extra Fee
|
| コンテスト | |
| ユーザー |
 nazcazcan
|
| 提出日時 | 2020-11-06 22:25:48 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 939 ms / 2,000 ms |
| コード長 | 8,305 bytes |
| コンパイル時間 | 3,872 ms |
| コンパイル使用メモリ | 249,228 KB |
| 実行使用メモリ | 98,940 KB |
| 最終ジャッジ日時 | 2024-11-16 06:43:34 |
| 合計ジャッジ時間 | 16,179 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
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)]));
}