結果
問題 | No.614 壊れたキャンパス |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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 secondtemplate<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;elsemini(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;elsemini(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;elsemini(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;}