結果

問題 No.614 壊れたキャンパス
ユーザー 0x19f0x19f
提出日時 2017-12-14 01:01:41
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 633 ms / 2,000 ms
コード長 1,599 bytes
コンパイル時間 2,349 ms
コンパイル使用メモリ 157,516 KB
実行使用メモリ 62,004 KB
最終ジャッジ日時 2023-08-21 02:43:49
合計ジャッジ時間 9,377 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
21,760 KB
testcase_01 AC 9 ms
21,740 KB
testcase_02 AC 7 ms
17,700 KB
testcase_03 AC 8 ms
17,652 KB
testcase_04 AC 8 ms
21,768 KB
testcase_05 AC 9 ms
21,776 KB
testcase_06 AC 8 ms
21,760 KB
testcase_07 AC 8 ms
17,680 KB
testcase_08 AC 531 ms
59,724 KB
testcase_09 AC 552 ms
57,776 KB
testcase_10 AC 500 ms
56,164 KB
testcase_11 AC 582 ms
61,724 KB
testcase_12 AC 633 ms
60,688 KB
testcase_13 AC 579 ms
60,780 KB
testcase_14 AC 558 ms
60,408 KB
testcase_15 AC 428 ms
56,788 KB
testcase_16 AC 492 ms
58,352 KB
testcase_17 AC 319 ms
50,884 KB
testcase_18 AC 305 ms
62,004 KB
testcase_19 AC 251 ms
56,392 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