제출 #753961

#제출 시각아이디문제언어결과실행 시간메모리
753961pavementSoccer (JOI17_soccer)C++17
35 / 100
2428 ms262144 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; //~ #define int long long #define mp make_pair #define mt make_tuple #define pb push_back #define ppb pop_back #define eb emplace_back #define g0(a) get<0>(a) #define g1(a) get<1>(a) #define g2(a) get<2>(a) #define g3(a) get<3>(a) #define g4(a) get<4>(a) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); using db = double; using ll = long long; using ld = long double; using ii = pair<int, int>; using iii = tuple<int, int, int>; using iiii = tuple<int, int, int, int>; using iiiii = tuple<int, int, int, int, int>; template<class key, class value = null_type, class cmp = less<key> > using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>; using lii = tuple<ll, int, int>; int H, W, N, sS, sT, eS, eT, dr[] = {-1, 0, 0, 1}, dc[] = {0, -1, 1, 0}, dist[505][505]; ll A, B, C, ans[505][505]; queue<iii> Q; priority_queue<lii, vector<lii>, greater<lii> > pq; main() { ios::sync_with_stdio(0); cin.tie(0); cin >> H >> W >> A >> B >> C >> N; H++; W++; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { dist[i][j] = (int)1e9; ans[i][j] = (ll)1e16; } } for (int i = 1, S, T; i <= N; i++) { cin >> S >> T; S++; T++; dist[S][T] = 0; Q.emplace(0, S, T); if (i == 1) sS = S, sT = T; else if (i == N) eS = S, eT = T; } while (!Q.empty()) { auto [d, r, c] = Q.front(); Q.pop(); if (d != dist[r][c]) continue; for (int k = 0; k < 4; k++) { int nr = r + dr[k], nc = c + dc[k]; if (1 <= nr && nr <= H && 1 <= nc && nc <= W && dist[nr][nc] > d + 1) { dist[nr][nc] = d + 1; Q.emplace(d + 1, nr, nc); } } } ans[sS][sT] = 0; pq.emplace(0, sS, sT); while (!pq.empty()) { auto [d, r, c] = pq.top(); assert(1 <= r && r <= H && 1 <= c && c <= W); pq.pop(); if (d != ans[r][c]) continue; if (r == eS && c == eT) { cout << d << '\n'; return 0; } for (int k = 1; k <= H; k++) { ll c1 = d + C * llabs(k - r); ll c2 = d + A * llabs(k - r) + B + C * dist[k][c]; ll cur = min(c1, c2); if (ans[k][c] > cur) { ans[k][c] = cur; pq.emplace(ans[k][c], k, c); } } for (int k = 1; k <= W; k++) { ll c1 = d + C * llabs(k - c); ll c2 = d + A * llabs(k - c) + B + C * dist[r][k]; ll cur = min(c1, c2); if (ans[r][k] > cur) { ans[r][k] = cur; pq.emplace(ans[r][k], r, k); } } } }

컴파일 시 표준 에러 (stderr) 메시지

soccer.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...