結果

問題 No.614 壊れたキャンパス
ユーザー femtofemto
提出日時 2017-12-14 01:17:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,037 ms / 2,000 ms
コード長 1,858 bytes
コンパイル時間 2,361 ms
コンパイル使用メモリ 200,072 KB
実行使用メモリ 65,272 KB
最終ジャッジ日時 2024-12-14 10:46:48
合計ジャッジ時間 12,981 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
12,016 KB
testcase_01 AC 5 ms
12,012 KB
testcase_02 AC 6 ms
12,008 KB
testcase_03 AC 5 ms
12,012 KB
testcase_04 AC 5 ms
12,144 KB
testcase_05 AC 6 ms
12,012 KB
testcase_06 AC 4 ms
12,020 KB
testcase_07 AC 6 ms
12,016 KB
testcase_08 AC 898 ms
60,744 KB
testcase_09 AC 955 ms
59,812 KB
testcase_10 AC 468 ms
62,012 KB
testcase_11 AC 1,025 ms
60,624 KB
testcase_12 AC 1,037 ms
60,740 KB
testcase_13 AC 1,019 ms
61,028 KB
testcase_14 AC 918 ms
61,480 KB
testcase_15 AC 429 ms
61,748 KB
testcase_16 AC 854 ms
61,128 KB
testcase_17 AC 592 ms
65,272 KB
testcase_18 AC 512 ms
45,724 KB
testcase_19 AC 553 ms
54,164 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;
vector<int> F[200000];
map<P, int> to; // building floor-> next floor

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