結果
| 問題 | No.2328 Build Walls |
| ユーザー |
 AngrySadEight
|
| 提出日時 | 2023-05-28 15:58:55 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,769 bytes |
| コンパイル時間 | 5,645 ms |
| コンパイル使用メモリ | 230,048 KB |
| 実行使用メモリ | 117,476 KB |
| 最終ジャッジ日時 | 2023-08-27 13:34:01 |
| 合計ジャッジ時間 | 38,129 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | AC | 1 ms
4,380 KB |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 1,021 ms
25,644 KB |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | AC | 141 ms
5,500 KB |
| testcase_20 | WA | - |
| testcase_21 | AC | 891 ms
16,056 KB |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | AC | 1,868 ms
28,180 KB |
| testcase_29 | WA | - |
| testcase_30 | AC | 1,908 ms
44,888 KB |
| testcase_31 | AC | 1,899 ms
40,168 KB |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | AC | 1,925 ms
46,536 KB |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
ソースコード
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <cassert>
#include <ctime>
#include <utility>
#include <random>
#include <tuple>
#include <bitset>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define repk(i, k, n) for (int i = k; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define mod1 1000000007
#define mod2 998244353
#define mod3 100000007
#define vi vector<int>
#define vs vector<string>
#define vc vector<char>
#define vl vector<ll>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vvc vector<vector<char>>
#define vvl vector<vector<ll>>
#define vvb vector<vector<bool>>
#define vvvi vector<vector<vector<int>>>
#define vvvl vector<vector<vector<ll>>>
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define vvpii vector<vector<pair<int,int>>>
#define vvpll vector<vector<pair<ll,ll>>>
template<typename T> void debug(T e){
cerr << e << endl;
}
template<typename T> void debug(vector<T> &v){
rep(i, v.size()){
cerr << v[i] << " ";
}
cerr << endl;
}
template<typename T> void debug(vector<vector<T>> &v){
rep(i, v.size()){
rep(j, v[i].size()){
cerr << v[i][j] << " ";
}
cerr << endl;
}
}
template<typename T> void debug(vector<pair<T, T>> &v){
rep(i,v.size()){
cerr << v[i].first << " " << v[i].second << endl;
}
}
template<typename T> void debug(set<T> &st){
for (auto itr = st.begin(); itr != st.end(); itr++){
cerr << *itr << " ";
}
cerr << endl;
}
template<typename T> void debug(multiset<T> &ms){
for (auto itr = ms.begin(); itr != ms.end(); itr++){
cerr << *itr << " ";
}
cerr << endl;
}
template<typename T> void debug(map<T, T> &mp){
for (auto itr = mp.begin(); itr != mp.end(); itr++){
cerr << itr->first << " " << itr->second << endl;
}
}
void debug_out(){
cerr << endl;
}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << " ";
debug_out(T...);
}
ll my_pow(ll x, ll n, ll mod){
// 繰り返し二乗法．x^nをmodで割った余り．
ll ret;
if (n == 0){
ret = 1;
}
else if (n % 2 == 1){
ret = (x * my_pow((x * x) % mod, n / 2, mod)) % mod;
}
else{
ret = my_pow((x * x) % mod, n / 2, mod);
}
return ret;
}
ll inv(ll x, ll mod){
return my_pow(x, mod - 2, mod);
}
void dijkstra(vvpll &graph, ll v, vl &dist){
priority_queue<pll, vpll, greater<pll>> pque;
pque.push(pll(0, v));
dist[v] = 0;
while(pque.size()){
pll p = pque.top();
pque.pop();
if (dist[p.second] != p.first){
continue;
}
for (auto x: graph[p.second]){
if (dist[x.first] > dist[p.second] + x.second){
dist[x.first] = dist[p.second] + x.second;
pque.push(pll(dist[x.first], x.first));
}
}
}
}
int main(){
ll H, W;
cin >> H >> W;
vvl A(H, vl(W));
for (ll i = 1; i < H - 1; i++){
for (ll j = 0; j < W; j++){
cin >> A[i][j];
}
}
ll INF = 100000000000000;
// 最短経路問題？
vector<ll> dist(H * W + 2, INF);
dist[H * W] = 0;
vector<vector<pll>> graph(H * W + 2, vpll(0));
for (ll i = 1; i < H - 1; i++){
if (A[i][0] != -1){
graph[H * W].push_back(pll(i * W, A[i][0]));
}
}
for (ll i = 1; i < H - 1; i++){
if (A[i][W - 1] != -1){
graph[i * W + (W - 1)].push_back(pll(H * W + 1, 0));
}
}
for (ll i = 1; i < H - 1; i++){
for (ll j = 0; j < W; j++){
if (A[i][j] == -1){
continue;
}
if (A[i - 1][j] != -1){
graph[i * W + j].push_back(pll((i - 1) * W + j, A[i - 1][j]));
}
if (A[i + 1][j] != -1){
graph[i * W + j].push_back(pll((i + 1) * W + j, A[i + 1][j]));
}
if (j > 0){
if (A[i][j - 1] != -1){
graph[i * W + j].push_back(pll(i * W + j - 1, A[i][j - 1]));
}
}
if (j < W - 1){
if (A[i][j + 1] != -1){
graph[i * W + j].push_back(pll(i * W + j + 1, A[i][j + 1]));
}
}
if (j > 0){
if (A[i - 1][j - 1] != -1){
graph[i * W + j].push_back(pll((i - 1) * W + j - 1, A[i - 1][j - 1]));
}
if (A[i + 1][j - 1] != -1){
graph[i * W + j].push_back(pll((i + 1) * W + j - 1, A[i + 1][j - 1]));
}
}
if (j < W - 1){
if (A[i - 1][j + 1] != -1){
graph[i * W + j].push_back(pll((i - 1) * W + j + 1, A[i - 1][j + 1]));
}
if (A[i + 1][j + 1] != -1){
graph[i * W + j].push_back(pll((i + 1) * W + j + 1, A[i + 1][j + 1]));
}
}
}
}
//dijkstra(graph, H * W, dist);
debug(dist);
if (dist[H * W + 1] == INF){
cout << -1 << endl;
}
else{
cout << dist[H * W + 1] << endl;
}
}