結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0