結果
問題 | No.614 壊れたキャンパス |
ユーザー |
![]() |
提出日時 | 2017-12-14 01:18:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,029 ms / 2,000 ms |
コード長 | 1,841 bytes |
コンパイル時間 | 2,357 ms |
コンパイル使用メモリ | 200,056 KB |
実行使用メモリ | 65,148 KB |
最終ジャッジ日時 | 2024-12-14 10:47:04 |
合計ジャッジ時間 | 12,674 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> P;typedef tuple<ll, int, int> State; // dist, building, floorconst ll INF = 1LL << 60;map<P, int> vmap;map<P, vector<int>> nxt; // building floor-> next floorvector<int> F[200000];ll dist[500000];int main(){cin.tie(0);ios::sync_with_stdio(false);#ifdef LOCALstd::ifstream in("in");std::cin.rdbuf(in.rdbuf());#endifint N, M, K, S, T;cin >> N >> M >> K >> S >> T;F[0].push_back(S);F[N - 1].push_back(T);for(int i = 0; i < M; i++){int a, b, c;cin >> a >> b >> c;a--;F[a].push_back(b);F[a + 1].push_back(c);nxt[{a, b}].push_back(c);}int V = 0;for(int i = 0; i < N; i++){sort(F[i].begin(), F[i].end());F[i].erase(unique(F[i].begin(), F[i].end()), F[i].end());for(auto f : F[i]){vmap[{i, f}] = V++;}}P start = { 0, S };P goal = { N - 1, T };if(vmap.count(start) == 0) vmap[start] = V++;if(vmap.count(goal) == 0) vmap[goal] = V++;fill((ll*)begin(dist), (ll*)end(dist), INF);dist[vmap[start]] = 0;priority_queue<State, vector<State>, greater<State>> q;q.push({ 0, 0, S });while(q.size()){ll d;int b, f;tie(d, b, f) = q.top();q.pop();if(nxt.count({ b, f })){for(auto nc : nxt[{b, f}]){State ns = { d, b + 1, nc };if(dist[vmap[{ b + 1, nc }]] > d){dist[vmap[{ b + 1, nc }]] = d;q.push(ns);}}}int idx = lower_bound(F[b].begin(), F[b].end(), f) - F[b].begin();for(int i = idx - 1; i <= idx + 1; i += 2){if(i < 0 || F[b].size() <= i) continue;ll nd = d + abs(f - F[b][i]);State ns = { nd, b, F[b][i] };if(dist[vmap[{ b, F[b][i] }]] > nd){dist[vmap[{ b, F[b][i] }]] = nd;q.push(ns);}}}if(dist[vmap[goal]] == INF) cout << -1 << endl;else cout << dist[vmap[goal]] << endl;}