結果

問題 No.614 壊れたキャンパス
ユーザー 0x19f
提出日時 2017-12-14 01:01:41
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 619 ms / 2,000 ms
コード長 1,599 bytes
コンパイル時間 1,714 ms
コンパイル使用メモリ 173,064 KB
実行使用メモリ 62,828 KB
最終ジャッジ日時 2024-12-14 10:40:56
合計ジャッジ時間 8,615 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
#define INF (1LL << 60)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

ll N, M, K, S, T, A[200000], B[200000], C[200000];
vector<pll> V, E[600000];

int main(void) {
  cin >> N >> M >> K >> S >> T;
  S--; T--;
  REP(i, 0, M) {
    cin >> A[i] >> B[i] >> C[i];
    A[i]--; B[i]--; C[i]--;
    V.push_back(pll(A[i], B[i]));
    V.push_back(pll(A[i] + 1, C[i]));
  }
  V.push_back(pll(0, S));
  V.push_back(pll(N - 1, T));

  sort(V.begin(), V.end());
  V.erase(unique(V.begin(), V.end()), V.end());

  REP(i, 0, V.size() - 1) {
    if(V[i].first == V[i + 1].first) {
      ll d = abs(V[i].second - V[i + 1].second);
      E[i].push_back(pll(i + 1, d));
      E[i + 1].push_back(pll(i, d));
    }
  }
  REP(i, 0, M) {
    ll b = lower_bound(V.begin(), V.end(), pll(A[i], B[i])) - V.begin();
    ll c = lower_bound(V.begin(), V.end(), pll(A[i] + 1, C[i])) - V.begin();
    E[b].push_back(pll(c, 0));
  }

  ll s = lower_bound(V.begin(), V.end(), pll(0, S)) - V.begin();
  ll g = lower_bound(V.begin(), V.end(), pll(N - 1, T)) - V.begin();

  priority_queue<pll, vector<pll>, greater<pll> > q;
  q.push(pll(0, s));
  vector<ll> dp(V.size(), INF);
  while(q.size()) {
    ll d = q.top().first;
    ll v = q.top().second;
    q.pop();

    if(dp[v] <= d) continue;
    dp[v] = d;

    if(v == g) break;

    REP(i, 0, E[v].size()) {
      ll nd = d + E[v][i].second;
      ll nv = E[v][i].first;
      if(dp[nv] > d) q.push(pll(nd, nv));
    }
  }
  cout << (dp[g] != INF ? dp[g] : -1) << endl;
}
0