結果

問題 No.614 壊れたキャンパス
ユーザー femtofemto
提出日時 2017-12-14 01:16:17
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
10,440 KB
testcase_01 AC 5 ms
10,436 KB
testcase_02 AC 6 ms
10,444 KB
testcase_03 AC 6 ms
10,568 KB
testcase_04 AC 6 ms
10,572 KB
testcase_05 AC 6 ms
10,564 KB
testcase_06 AC 4 ms
10,568 KB
testcase_07 AC 5 ms
10,440 KB
testcase_08 RE -
testcase_09 RE -
testcase_10 WA -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 WA -
testcase_16 RE -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

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;
}
0