結果

問題 No.614 壊れたキャンパス
ユーザー srup٩(๑`н´๑)۶srup٩(๑`н´๑)۶
提出日時 2017-12-14 13:13:34
言語 C++11
(gcc 11.4.0)
結果
MLE  
実行時間 -
コード長 2,732 bytes
コンパイル時間 1,834 ms
コンパイル使用メモリ 184,924 KB
実行使用メモリ 653,324 KB
最終ジャッジ日時 2024-12-14 12:39:06
合計ジャッジ時間 35,402 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
36,240 KB
testcase_01 MLE -
testcase_02 AC 11 ms
35,300 KB
testcase_03 AC 11 ms
200,348 KB
testcase_04 AC 11 ms
36,024 KB
testcase_05 MLE -
testcase_06 AC 12 ms
35,604 KB
testcase_07 MLE -
testcase_08 TLE -
testcase_09 MLE -
testcase_10 AC 1,825 ms
198,848 KB
testcase_11 MLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 MLE -
testcase_16 TLE -
testcase_17 AC 899 ms
99,408 KB
testcase_18 TLE -
testcase_19 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


int N, M, K, S, T;
int a[200010], b[200010], c[200010];
map<pair<int, int>, int> ma;

const int MAX_N = 500010;
using TYPE = ll; // 距離の型を入れる
vector<pair<int, TYPE> > G[MAX_N];
vector<TYPE> dijkstra(int start){
	vector<TYPE> dist(MAX_N, INFF);
	dist[start] = 0;//dist[i] :=　start->iまでの最短距離
	priority_queue<pair<TYPE, int>, vector<pair<TYPE, int> >, greater<pair<TYPE, int> > >  que;
	que.push(make_pair(0, start));
	while(!que.empty()){
		TYPE cost; int u;//今までにかかった時間 現在の頂点
		cost = que.top().first, u = que.top().second;
		que.pop();
		if(dist[u] < cost) continue;
		for (auto tmp : G[u]){
			int v = tmp.first; TYPE time = tmp.second;//隣接する頂点 その頂点まで行く時間
			if(dist[v] > dist[u] + time){//u->v
				dist[v] = dist[u] + time;
				que.push(make_pair(dist[v], v));
			}
		}
	}
	return dist;
}

set<int> li[200010]; // li[i] := i練で使われる階

int main(void) {
	cin >> N >> M >> K >> S >> T;
	rep(i, M) cin >> a[i] >> b[i] >> c[i];

	
	int cnt = 0;
	ma[mp(1, S)] = cnt++;
	ma[mp(N, T)] = cnt++;
	rep(i, M) {
		if(ma.count(mp(a[i], b[i])) == 0) ma[mp(a[i], b[i])] = cnt++;
		if(ma.count(mp(a[i] + 1, c[i])) == 0) ma[mp(a[i] + 1, c[i])] = cnt++;
	}

	// for(auto u : ma) printf("ma %d %d %d\n", u.fi.fi, u.fi.se, u.se);
	rep(i, M) {
		int u = ma[mp(a[i], b[i])], v = ma[mp(a[i] + 1, c[i])];
		// printf("u %d v %d\n", u, v);
		G[u].pb(mp(v, 0));
	}


	li[1].insert(S), li[N].insert(T);
	rep(i, M) {
		li[a[i]].insert(b[i]), li[a[i] + 1].insert(c[i]);
	}

	reps(i, 1, N + 1) {
		for(auto j : li[i])for(auto k : li[i]) {
			if(j == k) continue;
			// printf("j %d k %d\n", j, k);
			int u = ma[mp(i, j)], v = ma[mp(i, k)];
			// printf("2 u %d v %d\n", u, v);
			G[u].pb(mp(v, abs(j - k))), G[v].pb(mp(u, abs(j - k)));
		}
	}

	/*
	rep(i, 3) for(auto u : G[i]) {
		printf("%d -> %d %lld\n", i, u.fi, u.se);
	}
	*/
	

	auto dist = dijkstra(ma[mp(1, S)]);
	ll ans = dist[ma[mp(N, T)]];
	if(ans == INFF) printf("-1\n");
	else printf("%lld\n", ans);
	
	return 0;
}
0