結果

問題 No.614 壊れたキャンパス
ユーザー okadukiokaduki
提出日時 2017-12-18 17:18:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 207 ms / 2,000 ms
コード長 2,553 bytes
コンパイル時間 2,275 ms
コンパイル使用メモリ 187,124 KB
実行使用メモリ 17,148 KB
最終ジャッジ日時 2024-12-16 00:08:01
合計ジャッジ時間 4,461 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

void order(map<LL,LL>& m){
  PLL prv(-1, -1);
  for(auto& p: m){
	if(prv.FF >= 0){
	  mini(p.SS, abs(p.FF - prv.FF) + prv.SS);
	}

	prv = p;
  }

  prv = MP(-1,-1);
  for(auto rit=m.rbegin();rit!=m.rend();++rit){
	if(prv.FF >= 0){
	  mini(rit->SS, abs(rit->FF - prv.FF) + prv.SS);
	}

	prv = *rit;
  }
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, M;
  LL K, S, T;
  cin >> N >> M >> K >> S >> T;

  vector<vector<PII>> as(N-1);
  REP(i,M){
	int a, b, c;
	cin >> a >> b >> c;
	as[a-1].EB(b,c);
  }
  REP(i,N-1) SORT(as[i]);

  map<LL,LL> dp[2];
  int crt = 0, nxt = 1;
  dp[crt][S] = 0;
  REP(a,N-1){
	if(dp[crt].empty()){
	  break;
	}
	dp[nxt].clear();
	order(dp[crt]);

	auto it = begin(dp[crt]);
	auto nit = it;
	++nit;

	for(auto& p: as[a]){
	  while(nit != end(dp[crt]) && nit->FF < p.FF){
		LL cost = abs(it->FF - p.FF) + it->SS;
		if(!dp[nxt].count(p.SS))
		  dp[nxt][p.SS] = cost;
		else
		  mini(dp[nxt][p.SS], cost);
		++it;
		++nit;
	  }
	  LL cost = abs(it->FF - p.FF) + it->SS;
	  if(!dp[nxt].count(p.SS))
		dp[nxt][p.SS] = cost;
	  else
		mini(dp[nxt][p.SS], cost);
	  
	  if(nit != end(dp[crt])){
		LL cost = abs(nit->FF - p.FF) + nit->SS;
		if(!dp[nxt].count(p.SS))
		  dp[nxt][p.SS] = cost;
		else
		  mini(dp[nxt][p.SS], cost);
	  }
	}
	swap(crt, nxt);
  }

  if(dp[crt].empty()){
	cout << -1 << endl;
  }
  else{
	LL ans = 1e18;
	for(auto& p: dp[crt])
	  mini(ans, abs(p.FF - T) + p.SS);
	cout << ans << endl;
  }

  return 0;
}
0