結果

問題 No.614 壊れたキャンパス
ユーザー femto
提出日時 2017-12-14 01:16:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,858 bytes
コンパイル時間 2,374 ms
コンパイル使用メモリ 201,204 KB
実行使用メモリ 63,560 KB
最終ジャッジ日時 2024-12-14 10:45:46
合計ジャッジ時間 15,595 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 8 WA * 5 RE * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<ll, int, int> State; // dist, building, floor
const ll INF = 1LL << 60;
map<P, int> vmap;
map<P, vector<int>> nxt;
vector<int> F[200000];
map<P, int> to; // building floor-> next floor
ll dist[300000];
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
#ifdef LOCAL
std::ifstream in("in");
std::cin.rdbuf(in.rdbuf());
#endif
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0