結果

問題 No.614 壊れたキャンパス
ユーザー femtofemto
提出日時 2017-12-14 01:18:25
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 974 ms / 2,000 ms
コード長 1,841 bytes
コンパイル時間 2,443 ms
コンパイル使用メモリ 196,696 KB
実行使用メモリ 65,052 KB
最終ジャッジ日時 2023-08-21 02:50:32
合計ジャッジ時間 12,311 ms
ジャッジサーバーID
(参考情報)
judge14 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
12,172 KB
testcase_01 AC 5 ms
11,964 KB
testcase_02 AC 5 ms
11,984 KB
testcase_03 AC 5 ms
11,936 KB
testcase_04 AC 5 ms
11,940 KB
testcase_05 AC 5 ms
11,996 KB
testcase_06 AC 4 ms
12,012 KB
testcase_07 AC 4 ms
11,964 KB
testcase_08 AC 855 ms
60,544 KB
testcase_09 AC 919 ms
59,704 KB
testcase_10 AC 442 ms
62,108 KB
testcase_11 AC 974 ms
60,688 KB
testcase_12 AC 974 ms
60,672 KB
testcase_13 AC 974 ms
60,856 KB
testcase_14 AC 862 ms
61,336 KB
testcase_15 AC 387 ms
61,524 KB
testcase_16 AC 790 ms
61,208 KB
testcase_17 AC 585 ms
65,052 KB
testcase_18 AC 502 ms
45,408 KB
testcase_19 AC 540 ms
53,804 KB
権限があれば一括ダウンロードができます

ソースコード

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; // building floor-> next floor
vector<int> F[200000];
ll dist[500000];

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