제출 #683055

#제출 시각아이디문제언어결과실행 시간메모리
683055anonimy오벨리스크 (NOI14_obelisk)C++14
12 / 25
102 ms33292 KiB
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <functional> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; vector<vector<pll>> G; vector<ll> dist; ll m; ll dist1D(ll x, bool hor, bool ver) { if (m == 1) return x; if (!x) return 0; if (!hor && !ver) return 1e18; if (!hor) return x; ll v = x / (m + 1); ll sx = v * (m + 1); if (!x % (m + 1)) return 2 * v - 2; if (!ver) return 1e18; ll forw = max<ll>(2 * v - 2, 0) + x - sx; ll back = v * 2 + sx + m + 1 - x; return min<ll>(forw, back); } ll dist2D(pll a, pll b) { ll x = abs(a.first - b.first), y = abs(a.second - b.second); ll ans = 1e18; for (ll hor = 0; hor < 2; hor++) for (ll ver = 0; ver < 2; ver++) ans = min<ll>(ans, 2 * (hor + ver) + dist1D(x, hor, ver) + dist1D(y, hor, ver)); return ans; } void dijkstra(ll s) { dist.resize(G.size(), 1e18); vector<bool> visited(G.size(), false); priority_queue<pll, vector<pll>, greater<pll>> pq; dist[s] = 0; pq.push({ 0, s }); while (!pq.empty()) { ll v = pq.top().second; pq.pop(); if (visited[v]) continue; visited[v] = true; for (ll i = 0; i < G[v].size(); i++) { ll u = G[v][i].first, w = G[v][i].second; if (dist[v] + w < dist[u]) { dist[u] = dist[v] + w; pq.push({ dist[u], u }); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll k; cin >> k >> m; pll s, e; cin >> s.first >> s.second >> e.first >> e.second; vector<vector<pll>> floors(k + 1); floors[0].push_back(s); ll cnt = 2; for (ll i = 1; i < k; i++) { ll c; cin >> c; for (ll j = 0; j < c; j++) { pll x; cin >> x.first >> x.second; floors[i].push_back(x); cnt++; } } floors.back().push_back(e); G.resize(cnt); ll id = 0; for (ll i = 0; i < k; i++) { for (ll j = 0; j < floors[i].size(); j++) { for (ll k = 0; k < floors[i + 1].size(); k++) { ll v = id + j, u = id + floors[i].size() + k; ll w = dist2D(floors[i][j], floors[i + 1][k]); G[v].push_back({ u, w }); } } id += floors[i].size(); } dijkstra(0); cout << (dist.back()!=1e18?dist.back():-1); } /* 2 2 3 4 3 2 3 3 3 1 2 5 1 */

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

obelisk.cpp: In function 'void dijkstra(ll)':
obelisk.cpp:64:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (ll i = 0; i < G[v].size(); i++)
      |                  ~~^~~~~~~~~~~~~
obelisk.cpp: In function 'int main()':
obelisk.cpp:109:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (ll j = 0; j < floors[i].size(); j++)
      |                  ~~^~~~~~~~~~~~~~~~~~
obelisk.cpp:111:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    for (ll k = 0; k < floors[i + 1].size(); k++)
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...