結果

問題 No.614 壊れたキャンパス
ユーザー 0x19f0x19f
提出日時 2017-12-14 01:01:41
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 633 ms / 2,000 ms
コード長 1,599 bytes
コンパイル時間 1,534 ms
コンパイル使用メモリ 170,988 KB
実行使用メモリ 61,120 KB
最終ジャッジ日時 2024-05-08 08:15:33
合計ジャッジ時間 8,542 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
17,408 KB
testcase_01 AC 8 ms
17,408 KB
testcase_02 AC 8 ms
17,408 KB
testcase_03 AC 7 ms
17,536 KB
testcase_04 AC 8 ms
17,408 KB
testcase_05 AC 9 ms
17,408 KB
testcase_06 AC 8 ms
17,408 KB
testcase_07 AC 9 ms
17,408 KB
testcase_08 AC 525 ms
59,544 KB
testcase_09 AC 546 ms
57,560 KB
testcase_10 AC 507 ms
56,004 KB
testcase_11 AC 561 ms
60,332 KB
testcase_12 AC 633 ms
60,256 KB
testcase_13 AC 575 ms
60,360 KB
testcase_14 AC 550 ms
59,916 KB
testcase_15 AC 426 ms
56,612 KB
testcase_16 AC 476 ms
58,168 KB
testcase_17 AC 340 ms
50,884 KB
testcase_18 AC 324 ms
61,120 KB
testcase_19 AC 263 ms
55,628 KB
権限があれば一括ダウンロードができます

ソースコード

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